One day a highly important task was commissioned to Ed — writing a program in a night. The program consists of n lines of code. Ed is already exhausted, so he works like this: first he writes v lines of code, drinks a cup of tea, then he writes as much as ⌊v / k⌋ , drinks another cup of tea, then he writes ⌊v / k2⌋ lines and so on: ⌊v / k3⌋, ⌊v / k4⌋, ⌊v / k5⌋, … The moment the current value ⌊v / kp⌋ becomes 0, Ed immediately falls asleep, and he wakes up only in the morning; by this time, the program should already be finished. Ed is wondering: what minimum value of v can allow him write at least n lines of code before he falls asleep?
Input Format
The first line of input has an integer, which is the number of test cases T. Each of the following T lines consists of two integers n and k, separated by spaces. The first integer, n, is the size of Ed's program (in lines) where 1 ≤ n ≤ 109, and the second integer, k, is Ed's productivity reduction coefficient where 2 ≤ k ≤ 10.
Sample Input
3
7 2
59 9
1 9
Output Format The output should consist of T lines. The ith line should have the answer to the ith test case.
Sample Output
4
54
1
You must be logged in to submit a solution.