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$