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 は、指定した位置から始めて、いくつかの三つ組が最初に現れる位置を見つけるのを手伝ってほしいと思っています。彼を手伝ってもらえますか？

入力

最初の行には 2 つの整数 $n$ と $p$（$1 \le n \le 5000$、$1 \le p \le 2^{30}$）が与えられます。$n$ は質問の数を表し、$p$ は以降のすべての質問を法 $p$ で考えることを表します。

続く $n$ 行には、それぞれ 4 つの整数 $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$ を求める質問を表します。

出力

各質問について、その答えを表す整数を 1 行に出力してください。そのような整数 $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$ です。

2 番目の入出力例では、 $(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$ です。