我们考虑斐波那契数列 $f$，其中 $f(0) = 0$，$f(1) = 1$，且对于 $n \ge 2$ 有 $f(n) = f(n - 1) + f(n - 2)$。对于给定的 $x(0)$，可以定义另一个序列 $x$，满足 $x(n) = f(x(n - 1))$。现在你需要找到最小的 $n$，使得 $x(n) \equiv x(0) \pmod p$。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。

接下来对于每个测试用例，包含一行两个整数 $x(0)$ 和 $p$，其中 $0 \le x(0) \le 10^9$ 且 $1 \le p \le 200000$。

输出格式

对于每个测试用例，在一行中输出最小的 $n$，如果不存在这样的 $n$ 则输出 $-1$。

样例

输入样例 1

5
6 4
8 11
9 11
12 11
13 11

输出样例 1

3
3
-1
1
1

说明

在第一个样例中，$x(0) = 6 \equiv 2 \pmod 4$，$x(1) = f(6) = 8 \equiv 0 \pmod 4$ 且 $x(2) = f(8) = 21 \equiv 1 \pmod 4$，因此 $x(3) = f(21) = 10946 \equiv 2 \pmod 4$。