A85977.「WC2021」斐波那契

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

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

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

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

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

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

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

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

测试点编号	$n, m \le$	特殊限制
$1 \sim 2$	$1000$	无
$3 \sim 4$	${10}^5$	$m$ 是质数
$5 \sim 6$	${10}^5$	$m = p_1 p_2 \cdots p_k$，其中 $p_i$ 是两两不同的质数
$7 \sim 10$	${10}^5$	无