CF2169D2.Removal of a Sequence (Hard Version)

This is the hard version of the problem. The difference between the versions is the constraint on $x$; in this version, $x \le 10^{12}$.

Polycarp has a sequence of all natural numbers from $1$ to $10^{12}$. He decides to modify this sequence by performing the following action $x$ times:

• Simultaneously remove all numbers at positions $y$, $2 \cdot y$, $3 \cdot y$, ..., $m \cdot y \le n$, where $n$ is the length of the current sequence.

After that, Polycarp wants to find the $k$-th number in the remaining sequence or determine that the length of the resulting sequence is less than $k$.

Help Polycarp solve this problem!

Consider an example. Let $x = 2$, $y = 3$, $k = 5$, then:

The numbers crossed out with a red line were removed after the first operation, and the numbers crossed out with a blue line were removed after the second operation. Thus, the number at position $k = 5$ is the number $10$.

这是该问题的困难版本。两个版本的区别在于对 $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$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10$). The description of the test cases follows.

The only line of each test case contains three integers $x$, $y$, $k$ ($1 \le x, y, k \le 10^{12}$).

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10$）。随后是测试用例的描述。

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

For each test case, output a positive integer that is at the $k$-th position in the resulting sequence, or $-1$ if the length of the resulting sequence is less than $k$.

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