CF1982B Collatz Conjecture

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

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.

For each test case, output a single integer — the number obtained after applying $ k $ operations.

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