430. Military Service

Problem Statement:
You have just started your military service with the border guards. Since you are a Computer Science graduate, they asked you to implement a schedule for the soldiers. Initially no soldier is on duty and you need the schedule to satisfy 2 requirements:

- There are N soldiers, each soldier can be on duty for at most K continuous months and then he must take one month of vacation.
- The schedule needs to make sure that the guaranteed minimum number of soldiers on duty at any given time is maximized.

Given N and K, the system will calculate the maximum guaranteed number of soldiers to be on duty at any given time.

Input Format:
Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1 ≤ T ≤ 100).

Each test case consists of a line containing 2 space separated integers:
- N: The number of soldiers (0 ≤ N ≤ 10,000,000)
- K: The number of continuous months a soldier can be on duty before they have to take a month of vacation (0 ≤ K ≤ 10,000,000).

Output Format:
For each test case, print a single line containing the maximum guaranteed number of soldiers on duty at any given time.

Sample Input:
3 4 1 9 3 21 3

Sample Output:
2 6 15

 Added by: ahmed_aly Added at: 2016-11-26 17:00:00 UTC Time Limit: 2 seconds Partial score: No Source: ACM Arab Collegiate Programming Contest 2016