Peter has N cigarettes. He smokes them one by one keeping all the butts. Out of K > 1 butts he roll a new cigarette.

How many cigarettes can Peter have?

Input Format:
The first line of input contains an integer T indicating the number of test cases. T lines follow. Each line contains two integer numbers giving the values of N and K.

Output Format:
For each set of N and K, output one integer number giving the maximum number of cigarettes that Peter can smoke.

Constraints:
T ≤ 10
2 ≤ N, K ≤ 1 000 000 000