23498번 - Fraction Reduction 다국어

문제

Chiaki has a fraction $\frac{a}{b}$ (not necessary an irreducible fraction) and can perform the following 2ドル$ operations:

• If the current fraction is $x,ドル Chiaki can change it to $-\frac{1}{x}$.
• If the current fraction is $x,ドル Chiaki can change it to $x+1$.

Now, Chiaki would like to know the number of minimum operations needed to make $\frac{a}{b}$ become 0ドル$. Since this number may be very large, you are only asked to calculate it modulo 10ドル^9+7$.

입력

There are multiple test cases. The first line of the input contains an integer $T$ (1ドル \le T \le 10^5$), indicating the number of test cases. For each test case:

The first line contains two integers $a$ and $b$ ($-10^{18} \le a \le 10^{18}, 1 \le b \le 10^{18}$), denoting the fraction.

출력

For each test case, output an integer denoting the the number of minimum operations modulo 10ドル^9+7,ドル or $-1$ if there's no such operations to make $\frac{a}{b}$ become 0ドル$.

제한

노트

For the 1ドル$-st sample, you don't need any operations.

For the 2ドル$-nd sample, one possible sequence is: $\frac{1}{1} \to -\frac{1}{1} \to 0$.

For the 3ドル$-rd sample, one possible sequence is: $-\frac{1}{2} \to \frac{1}{2} \to -\frac{2}{1} \to -\frac{1}{1} \to 0$.

For the 4ドル$-th sample, one possible sequence is: $-\frac{2}{4} \to \frac{2}{4} \to -\frac{4}{2} \to -\frac{2}{2} \to 0$.

For the 5ドル$-th sample, one possible sequence is: $\frac{8}{5} \to -\frac{5}{8} \to \frac{3}{8} \to -\frac{8}{3} \to -\frac{5}{3} \to -\frac{2}{3} \to \frac{1}{3} \to -\frac{3}{1} \to -\frac{2}{1} \to -\frac{1}{1} \to 0$.