Collatz Conjecture
Contest: Codeforces Round 955 (Div. 2, with prizes from NEAR!)
Difficulty rating: 1200
Tags: brute force, implementation, math, number theory

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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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

Example input:
13
1 3 1
2 3 1
24 5 5
16 3 2
2 2 1
1337 18 1
1 2 144133
12345678 3 10
998244353 2 998244353
998244353 123456789 998244352
998244354 998241111 998244352
998244355 2 9982443
1000000000 1000000000 1000000000

Example output:
2
1
1
2
3
1338
1
16936
1
21180097
6486
1
2

Editorial:
Let's write down what happens in the problem and try to speed it up. The first observation: we will perform operations until $$$x \neq 1$$$, after which the answer can be found using the formula $$$ans = 1 + k\,\%\,(y - 1)$$$. Indeed, after $$$x$$$ becomes equal to $$$1$$$, if we continue applying operations to it, it will change as follows:
$$$$$$ 1 \to 2 \to ... \to (y - 1) \to 1 \to 2 \to ... \to (y - 1) \to 1 \to ... $$$$$$
The second optimization is to group the operations that only add one, so instead of $$$1$$$ we will add the next value to $$$x$$$ in one action $$$min(k, \lceil \frac{x}{y} \rceil \cdot y - x)$$$. After this (if we added at least $$$1$$$), we should try to divide the number by $$$y$$$ (if it is divisible).
If we use these two optimizations, our solution will work in $$$O(\log x)$$$ for one set of input data, since in one action $$$x$$$ decreases to $$$\lceil \frac{x + 1}{y} \rceil$$$, and therefore $$$x$$$ becomes $$$1$$$ in no more than $$$O(\log x)$$$ actions.