Description:
Recently, the first-year student Maxim learned about the Collatz conjecture, but he didn't pay much attention during the lecture, so he believes that the following process is mentioned in the conjecture:
There is a variable $$$x$$$ and a constant $$$y$$$. The following operation is performed $$$k$$$ times:
- increase $$$x$$$ by $$$1$$$, then
- while the number $$$x$$$ is divisible by $$$y$$$, divide it by $$$y$$$.
For example, if the number $$$x = 16$$$, $$$y = 3$$$, and $$$k = 2$$$, then after one operation $$$x$$$ becomes $$$17$$$, and after another operation $$$x$$$ becomes $$$2$$$, because after adding one, $$$x = 18$$$ is divisible by $$$3$$$ twice.
Given the initial values of $$$x$$$, $$$y$$$, and $$$k$$$, Maxim wants to know what is the final value of $$$x$$$.
Input Format:
Each test consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — the number of test cases. Then follows the description of the test cases.
The only line of each test case contains three integers $$$x$$$, $$$y$$$, and $$$k$$$ ($$$1 \le x, k \le 10^{9}$$$, $$$2 \le y \le 10^{9}$$$) — the initial variable, constant and the number of operations.
Output Format:
For each test case, output a single integer — the number obtained after applying $$$k$$$ operations.
Note:
In the first test case, there is only one operation applied to $$$x = 1$$$, resulting in $$$x$$$ becoming $$$2$$$.
In the second test case, for $$$x = 2$$$, within one operation, one is added to $$$x$$$ and it's divided by $$$y = 3$$$, resulting in $$$x$$$ becoming $$$1$$$.
In the third test case, $$$x$$$ changes as follows:
- After the first operation, $$$x = 1$$$, because $$$24 + 1 = 25$$$ and $$$25$$$ is divisible by $$$y = 5$$$ twice within one operation.
- After the second operation, $$$x = 2$$$.
- After the third operation, $$$x = 3$$$.
- After the fourth operation, $$$x = 4$$$.
- After the fifth operation, $$$x = 1$$$.