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_kb_k+b_kc_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,\ldots$

喺第二個樣例入面，$(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,\ldots$