Jeffery 发现了一个神奇的三元组序列 $\{(a_k, b_k, c_k)\}_{k=0}^{\infty}$：

• $(a_0, b_0, c_0) = (2, 1, 0)$；且
• 对于每个非负整数 $k$，$(a_{k+1}, b_{k+1}, c_{k+1}) = (a_k^2 + b_k^2, a_k b_k + b_k c_k, b_k^2 + c_k^2)$。

例如，$(a_1, b_1, c_1) = (5, 2, 1)$ 且 $(a_2, b_2, c_2) = (29, 12, 5)$。

如果我们考虑模整数 $p$ 下的序列，有些三元组永远不会出现在该序列中，有些三元组会周期性出现，而另一些三元组则只会出现一次。

Jeffery 想知道你是否能帮他找出从给定位置开始，某些三元组第一次出现的位置。你能帮帮他吗？

输入格式

第一行包含两个整数 $n$ 和 $p$ ($1 \le n \le 5000, 1 \le p \le 2^{30}$)，其中 $n$ 表示询问次数，$p$ 表示所有后续询问均在模 $p$ 意义下考虑。

接下来的 $n$ 行，每行包含四个整数 $x, y, z$ 和 $m$ ($0 \le x, y, z < p, 0 \le m \le 10^{18}$)，表示一个询问，要求你找到满足 $k \ge m$ 且 $(a_k, b_k, c_k) \equiv (x, y, z) \pmod p$ 的最小整数 $k$。

输出格式

对于每个询问，输出一行一个整数，表示该问题的答案。如果不存在这样的整数 $k$，则输出 $-1$。

样例

样例输入 1

5 11
6 1 4 10
4 10 6 3
7 1 5 0
2 1 0 1
2 1 0 0

样例输出 1

11
4
2
-1
0

样例输入 2

5 10
5 8 9 5
0 2 6 0
9 2 5 6
5 5 5 7
5 2 1 2

样例输出 2

5
-1
6
-1
-1

说明

在第一个样例中，$(a_0, b_0, c_0) \equiv (2, 1, 0)$，$(a_1, b_1, c_1) \equiv (5, 2, 1)$，$(a_2, b_2, c_2) \equiv (7, 1, 5)$，$(a_{2T+3}, b_{2T+3}, c_{2T+3}) \equiv (6, 1, 4)$，$(a_{2T+4}, b_{2T+4}, c_{2T+4}) \equiv (4, 10, 6) \pmod{11}$，其中 $T = 0, 1, 2, \dots$。

在第二个样例中，$(a_0, b_0, c_0) \equiv (2, 1, 0)$，$(a_1, b_1, c_1) \equiv (5, 2, 1)$，$(a_{2T+2}, b_{2T+2}, c_{2T+2}) \equiv (9, 2, 5)$，$(a_{2T+3}, b_{2T+3}, c_{2T+3}) \equiv (5, 8, 9) \pmod{10}$，其中 $T = 0, 1, 2, \dots$。