Alice mixed up the words transmutation and permutation! She has an array $a$ specified via three integers $n$, $b$, $c$: the array $a$ has length $n$ and is given via $a_i = b\cdot (i - 1) + c$ for $1\le i\le n$. For example, if $n=3$, $b=2$, and $c=1$, then $a=[2 \cdot 0 + 1, 2 \cdot 1 + 1, 2 \cdot 2 + 1] = [1, 3, 5]$.

Now, Alice really enjoys permutations of $[0, \ldots, n-1]$$^{\text{∗}}$ and would like to transform $a$ into a permutation. In one operation, Alice replaces the maximum element of $a$ with the $\operatorname{MEX}$$^{\text{†}}$ of $a$. If there are multiple maximum elements in $a$, Alice chooses the leftmost one to replace.

Can you help Alice figure out how many operations she has to do for $a$ to become a permutation for the first time? If it is impossible, you should report it.

$^{\text{∗}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $0$ to $n-1$ in arbitrary order. Please note, this is slightly different from the usual definition of a permutation. For example, $[1,2,0,4,3]$ is a permutation, but $[0,1,1]$ is not a permutation ($1$ appears twice in the array), and $[0,2,3]$ is also not a permutation ($n=3$ but there is $3$ in the array).$^{\text{†}}$The $\operatorname{MEX}$ of an array is the smallest non-negative integer that does not belong to the array. For example, the $\operatorname{MEX}$ of $[0, 3, 1, 3]$ is $2$ and the $\operatorname{MEX}$ of $[5]$ is $0$.

Input

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

The only line of each test case contains three integers $n$, $b$, $c$ ($1\le n\le 10^{18}$; $0\le b$, $c\le 10^{18}$) — the parameters of the array.

Output

For each test case, if the array can never become a permutation, output $-1$. Otherwise, output the minimum number of operations for the array to become a permutation.

Note

In the first test case, the array is already $[0, 1, \ldots, 9]$, so no operations are required.

In the third test case, the starting array is $[1, 3, 5, \ldots, 199]$. After the first operation, the $199$ gets transformed into a $0$. In the second operation, the $197$ gets transformed into a $2$. If we continue this, it will take exactly $50$ operations to get the array $[0, 1, 2, 3, \ldots, 99]$.

In the fourth test case, two operations are needed: $[1,1,1] \to [0,1,1] \to [0,2,1]$.

In the fifth test case, the process is $[0,0,0] \to [1,0,0] \to [2,0,0] \to [1,0,0] \to [2,0,0]$. This process repeats forever, so the array is never a permutation and the answer is $-1$.