시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

## 문제

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.

## 입력

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).

## 출력

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

## 예제 입력 1

3
4 1
9 3
21 3


## 예제 출력 1

2
6
15