Chiaki 有一个分数 $\frac{a}{b}$（不一定是最简分数），她可以进行以下两种操作：

• 如果当前分数为 $x$，Chiaki 可以将其变为 $-\frac{1}{x}$。
• 如果当前分数为 $x$，Chiaki 可以将其变为 $x + 1$。

现在，Chiaki 想知道将 $\frac{a}{b}$ 变为 $0$ 所需的最少操作次数。由于这个数字可能非常大，你只需要计算其对 $10^9 + 7$ 取模的结果。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试数据的组数。对于每组测试数据：

第一行包含两个整数 $a$ 和 $b$ ($-10^{18} \le a \le 10^{18}$, $1 \le b \le 10^{18}$)，表示该分数。

输出格式

对于每组测试数据，输出一个整数，表示最少操作次数对 $10^9 + 7$ 取模的结果；如果无法通过操作将 $\frac{a}{b}$ 变为 $0$，则输出 $-1$。

样例

样例输入 1

5
0 1
1 1
-1 2
-2 4
8 5

样例输出 1

0
2
4
4
10

说明

对于第 1 组样例，不需要任何操作。

对于第 2 组样例，一种可能的序列是：$\frac{1}{1} \to -\frac{1}{1} \to 0$。

对于第 3 组样例，一种可能的序列是：$-\frac{1}{2} \to \frac{1}{2} \to -\frac{2}{1} \to -\frac{1}{1} \to 0$。

对于第 4 组样例，一种可能的序列是：$-\frac{2}{4} \to \frac{2}{4} \to -\frac{4}{2} \to -\frac{2}{2} \to 0$。

对于第 5 组样例，一种可能的序列是：$\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$。