Polycarp 拥有一个包含从 $1$ 到 $10^{12}$ 的所有自然数的序列。他决定对该序列执行以下操作共 $x$ 次：

• 同时删除当前序列中位置为 $y$、$2 \cdot y$、$3 \cdot y$、……、$m \cdot y \le n$ 的所有数字，其中 $n$ 是当前序列的长度。

之后，Polycarp 希望找到剩余序列中的第 $k$ 个数字，或者判断最终序列的长度小于 $k$。

请帮助 Polycarp 解决此问题！

考虑一个例子。设 $x = 2$，$y = 3$，$k = 5$，则：

被红线划掉的数字是在第一次操作后被删除的，而被蓝线划掉的数字是在第二次操作后被删除的。因此，位置 $k = 5$ 上的数字是 $10$。

输入

每个测试包含多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 10$）。接下来是各测试用例的描述。

每个测试用例仅一行，包含三个整数 $x$、$y$、$k$（$1 \le x \le \bf{10^{5}}$，$1 \le y, k \le 10^{12}$）。

输出

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

Samples

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