Laoshan mineral water is one of famous well-known mineral water, Tyrant(means”Tu Hao”) Chierush liked to drink this mineral water very much. He said that it is such a natural taste, but this is not the focus. One day Chierush went to the campus supermarket to buy n bottles of Laoshan mineral water, the boss see that he is an acquaintance, so he gave him a copy of preferential policies - he can change every m empty bottles into one bottle mineral water. Your task is to help Chierush calculate how many bottles of mineral water he can drink?

The input consists of multiple test cases. The first line contains an integer T means the number of test cases. Each test case consists of one line with two numbers represent n and m. (T<=100, 2<=n,m<=2*10^9)

For each test case, output one line, including one number that represents the answer.

2
2 2
5 4

3
6

 

SDUST