该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

问题描述

吕学长有一个包含所有从 $1$ 到 $10^{12}$ 的自然数的序列。他决定对这个序列进行 $x$ 次如下操作来修改它：

• 同时移除当前序列中位于位置 $y, 2 \cdot y, 3 \cdot y, \dots, m \cdot y \le n$ 的所有数字，其中 $n$ 是当前序列的长度。

之后，吕学长想要找到剩余序列中的第 $k$ 个数字，或者确定最终序列的长度是否小于 $k$。

请帮助吕学长解决这个问题！

比如，设 $x = 2$，$y = 3$，$k = 5$，则：

第一次操作后移除的数字用红线划去，第二次操作后移除的数字用蓝线划去。 因此，位于位置 $k=5$ 的数字是 $10$。

输入格式

每个测试包含多组测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10$)。接下来是测试用例的描述。

每个测试用例只有一行，包含三个整数 $x$，$y$，$k$ ($1 \le x \le 10^5$，$1 \le y, k \le 10^{12}$)。

输出格式

对于每个测试用例，输出最终序列中第 $k$ 个位置上的正整数，如果最终序列的长度小于 $k$，则输出 $-1$。

样例

6
2 3 5
2 5 1
20 2 1000000000000
175 10 28
100000 998244353 1999999999
1 1 1

10
1
-1
2339030304
2000199999
-1