For the first test case:
You will get 7 bottles filled with water in return for 21 empty bottles and left with 1 empty bottle.
Now you have a total 8 (7 + 1) empty water bottles after using the water.
Again, you will get 2 bottles filled with water in return for 6 empty bottles and left with 2 empty bottles.
Now you have a total 4 (2 + 2) empty water bottles after using the water.
Again, you will get 1 bottles filled with water in return for 3 empty bottles and left with 1 empty bottle.
Now you have a total 2 (1 + 1) empty water bottles after using the water.
Therefore, the total number of bottles filled with water that you got is 7 + 2 + 1 = 10.

For the second test case:
You have only 7 empty bottles but need 10 at least to get a bottle filled with water. So, the answer will be 0.

For the third test case:
Similarly as first case, you will get total of 25 bottles filled with water for your use.

Updated problem name

Collecting water

Updated problem statement

You have collected \(n\) empty plastic bottles around your location.

A machine contains an infinite amount of water stored that accepts the empty plastic bottles and but in return, you get some plastic bottles that are filled with water. The machine works based on a rule which states that you get one plastic bottle that is filled with water for \(k\) empty plastic bottles.

You require water for yourself, therefore, you can use as many empty bottles as you can to get water. You must use the collected amount of water instantly and repeat the recycling process.

You are required to print the total number of bottles that are filled with water.

Input format

First line: A single integer \(t\) denoting the number of test cases
Next \(t\) lines: \(n\) and \(k\) two space-separated integers

Output format

Print a single integer in the next \(t\) lines.

Constraints

\(1 \leq t \leq 10^5\)

\(0 \leq n \leq 10^{18}\)

\(2 \leq k \leq 10^{18}\)