Juice

Problem

After an ACM training, Ho Leung suggested to have some drink together and he offered paying the bill. There were Ho Leung and 8 ACM members. Ho Leung wanted to pay as little as possible. Great! He found that ABC Juice had a special promotion. To encourage glass recycling, whenever four empty juice bottles were returned, a free bottle of juice would be given. After some calculation, he found that by paying for 7 bottles of juice only and returning the empty bottles, they could enjoy totally 9 bottles of juice. Then all members and him could have one bottle each. Hence, he chose ABC Juice!!!

Let us consider a more general question. Assume we pay for n bottles of juice and a free bottle will be given for every k empty bottles returned, how many bottles of juice can we enjoy at most?

Input

The first line contains an integer, specifying the number of test cases.
There will be at most 10000 cases.
For each case, there will be only one line with two integers n and k where 0 ≤ n ≤ 2³¹ and 2 ≤ k ≤ 2³¹.

Output

Each case should have one line of output, specifying the maximum number of bottles we can enjoy.

Sample Input

3
7 4
5 2
6 3

Sample Output

9
9
8

Author