CF1982B.Collatz Conjecture

最近，一年级新生 Maxim 了解到了 Collatz 猜想，但他在讲座上并没有认真听讲，所以他认为猜想中提到的是如下过程：

有一个变量 $x$ 和一个常数 $y$。进行 $k$ 次如下操作：

• 将 $x$ 增加 $1$，然后
• 当 $x$ 能被 $y$ 整除时，不断将 $x$ 除以 $y$。

注意，这两个动作在一次操作中依次进行。例如，如果 $x = 16$，$y = 3$，$k = 2$，那么第一次操作后 $x$ 变为 $17$，再进行一次操作后 $x$ 变为 $2$，因为加一后 $x = 18$，可以被 $3$ 连续整除两次。

给定 $x$、$y$ 和 $k$ 的初始值，Maxim 想知道经过 $k$ 次操作后 $x$ 的最终值。

每组测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^{4}$）——表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例一行，包含三个整数 $x$、$y$ 和 $k$（$1 \le x, k \le 10^{9}$，$2 \le y \le 10^{9}$）——初始变量、常数和操作次数。

对于每个测试用例，输出一个整数——经过 $k$ 次操作后得到的数。

在第一个测试用例中，只对 $x = 1$ 进行了一次操作，结果 $x$ 变为 $2$。

在第二个测试用例中，对于 $x = 2$，一次操作中先加一再除以 $y = 3$，结果 $x$ 变为 $1$。

在第三个测试用例中，$x$ 的变化如下：

• 第一次操作后，$x = 1$，因为 $24 + 1 = 25$，$25$ 可以被 $y = 5$ 连续整除两次。
• 第二次操作后，$x = 2$。
• 第三次操作后，$x = 3$。
• 第四次操作后，$x = 4$。
• 第五次操作后，$x = 1$。

由 ChatGPT 4.1 翻译