CFCF2169D2.Removal of a Sequence (Hard Version)

这是该问题的困难版本。不同之处在于本版本对 $x$ 的约束更大：$x \le 10^{12}$。

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, y, k \le 10^{12}$）。

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