Work Till You Drop

Ben has to complete a programming assignment overnight. He has to write n lines of code before morning. He is dead tired and he tries drinking some black coffee to keep him awake. But each time he drinks a cup of coffee he stays awake for a short amount of time but his productivity goes down by a constant factor k

This is how he plans to write the program. He will write the first v lines of code, then drink his first cup of coffee. Since his productivity has gone down by a factor of k. he will write v // k lines of code. He will have another cup of coffee and then write v // k**2 lines of code. He will have another cup of coffee and write v // k**3 lines of code and so on. He will collapse and fall asleep when v // k ** p becomes 0.

Now Ben does want to complete his assignment and maximize on his sleep. So he wants to figure out the minimum allowable value of v for a given productivity factor that will allow him to write at least n lines of code before he falls asleep.

Your input file will be called work.txt. Here is a typical file:

2 7 2 59 9 

The first line is T the number of test cases. This will be followed by T lines of input. Each line of input will have two numbers n and k. n is the number of lines of code to write and k is the productivity factor, where 1 n 10⁶ and 2 k 10.

For each test case, your output to the screen will be v lines of code the Ben has to write. For the above two test cases, the output will be:

4 54 

You have to modify the binary search algorithm to solve this problem.

(Additional test cases:

Inputs:

9

9 2 23 3 578 5 6728 7 12829 9 723890 11 5723948 13 48576598 16 394857939 22

Outputs:

6 17 465 5769 11406 658085 5283647 45540564 376909853)