4153. 终结星河

【题目描述】

小 L 希望成为文能寂静询问，武能终结星河的超级神人。但在此之前，她需要通过数学大神 aoao 的试炼。aoao 给出了一道数学题……

aoao 有三个正整数 $x, y, k$，你需要不断执行以下操作：

若 $x \bmod y \ne 0$，则将 $x$ 增加 $1$，并将 $k$ 减少 $1$.

若在任意时刻 $x \bmod y = 0$，则将 $x$ 除以 $y$.

当 $k=0$ 且 $x \bmod y \ne 0$ 时，游戏结束。

注：$x \bmod y$ 表示 $x$ 对 $y$ 取模得到的余数，在 C++ 中，你可以通过 $x \% y$ 获得这个值。

aoao 希望知道所有操作结束后的 $x$.

【输入格式】

第一行一个正整数 $T$，表示共 $T$ 组询问。

以下 $T$ 行，每行三个正整数 $x, y, k$，意义见【题目描述】。

【输出格式】

对每组测试数据，输出一行一个正整数，表示操作结束后的 $x$.

【样例输入】

5
16 3 1
16 3 2
16 3 3
4 2 2
1000000000 1000000000 1000000000

【样例输出】

17
2
1
1
2

【数据规模与约定】

对于 $30\%$ 的数据，$1 \le x, y, k \le 2000, y \ne 1$.

对于另外 $20\%$ 的数据，$k = 1$.

对于 $100 \%$ 的数据，$1 \le x, y, k \le 10^9$, $1 \le T \le 1000$, $y \ne 1$.

【来源】

校际联合邀请赛第6场语法组T4