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}\)