最近一年级学生Maxim了解到了Collatz猜想,但他在听课时并没有太注意,所以他认为猜想中提到了以下过程:
有一个变量 $$$x$$$ 和一个常量 $$$y$$$。以下操作执行 $$$k$$$ 次:
- 将 $$$x$$$ 增加 $$$1$$$,然后
- 当数字 $$$x$$$ 可以被 $$$y$$$ 整除时,将其除以 $$$y$$$。
例如,如果数字 $$$x = 16$$$、$$$y = 3$$$ 和 $$$k = 2$$$,则经过一次操作后 $$$x$$$ 变为 $$$17$$$,经过另一次操作后 $$$x$$$ 变为 $$$2$$$,因为加一后,$$$x = 18$$$ 可以整除$$$3$$$ 两次。
给定 $$$x$$$、$$$y$$$ 和 $$$k$$$ 的初始值,Maxim 想知道 $$$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$$$ 操作后获得的数字。
示例
输入 #1
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
输出 #1
2 1 1 2 3 1338 1 16936 1 21180097 6486 1 2
注意
在第一个测试用例中,只有一个操作应用于 $$$x = 1$$$,导致 $$$x$$$ 变为 $$$2$$$。
在第二个测试用例中,对于 $$$x = 2$$$,在一次操作中,$$$x$$$ 加一,然后除以 $$$y = 3$$$,导致 $$$x$$$ 变为 $$$1$$$。
在第三个测试用例中,$$$x$$$ 更改如下:
- 第一次运算后,$$$x = 1$$$,因为 $$$24 + 1 = 25$$$ 且 $$$25$$$ 在一次运算中可被 $$$y = 5$$$ 整除两次。
- 第二次操作后,$$$x = 2$$$。
- 第三次操作后,$$$x = 3$$$。
- 第四次操作后,$$$x = 4$$$。
- 第五次操作后,$$$x = 1$$$。