众所周知，小葱同学擅长计算，尤其擅长计算组合数。但是对组合数有了充分研究的小葱同学对组合数失去了兴趣，而开始研究数列。

我们定义 $F_0=a$，$F_1=b$，$F_i=(F_{i-1}+F_{i-2})modm$（$i\ge 2$）。

现在给定 $n$ 组询问，对于每组询问请找到一个最小的整数 $p$，使得 $F_p=0$。

输入格式

第一行两个整数 $n,m$，代表询问的组数和每组计算中的模数。

接下来 $n$ 行每行两个整数 $a,b$，代表一组询问中 $F_0$ 和 $F_1$ 的值。

输出格式

对于每组询问，输出一行一个整数 $p$ 代表答案。如果这样的 $p$ 不存在，输出 -1。

样例一

input

4 5
0 1
1 2
2 3
3 4

output

0
3
2
-1

样例二

input

1 6
4 4

output

3

样例三

见附加文件中 ex_fib3.in 与 ex_fib3.ans。

样例四

见附加文件中 ex_fib4.in 与 ex_fib4.ans。

限制与约定

对于所有测试点：$1\le n,m\le {10}^5$，$0\le a,b<m$。

每个测试点的具体限制见下表：

时间限制：$1\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

下载

样例数据下载