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$.

Note that both of these actions are performed sequentially within one operation.

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

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

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$.