这是问题的简单版本。版本之间的区别在于 $$$x$$$ 的约束;在此版本中,$$$x \le 10^5$$$。
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$$$。
示例
输入复制
62 3 52 5 120 2 1000000000000175 10 28100000 998244353 19999999991 1 1
输出复制
101-123390303042000199999-1