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