Nowadays out little Chef is traveling a lot. While traveling, on one unlucky day, he lost into a mysterious country. Nearby people handed little Chef to the King for investigations. After proper investigation they found little Chef innocent. Little Chef had no money with him to return to his country Byteland, so the King helped him by giving some money.

The monetary system of the country has coins of following values :
K^0 , K^1 , K^2 , K^3 , K^4 ..... (till infinity)
The King gave him K coins of each type.

The cost of the air ticket from that country to Byteland (his home) is N . What is the minimum number of coins little chef has to spend to buy a ticket ? Little Chef want to spend minimum number of coins so that he can play with the remaining coins in his home !

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

The only line of each test case contains two space separated integers N and K as described in the problem statement.

Output

For each test case, output a single line containing the answer to the corresponding test case.

Constraints

1 ≤ T ≤ 100,000
1 ≤ N ≤ 1,000,000,000,000,000,000 (10^18)
1 ≤ K ≤ 100,000

Example
Input:
2
12 2
18 3

Output:
2
2

见题面

见题面