Jeffery znalazł niezwykły ciąg trójek $\{(a_k,b_k,c_k)\}_{k=0}^{\infty}$:

• $(a_0,b_0,c_0)=(2,1,0)$; oraz

• dla każdej nieujemnej liczby całkowitej $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)$.

Na przykład $(a_1,b_1,c_1)=(5,2,1)$ i $(a_2,b_2,c_2)=(29,12,5)$.

Jeśli rozpatrujemy ciąg modulo pewna liczba całkowita $p$, niektóre trójki nigdy nie pojawią się w tym ciągu, niektóre będą pojawiać się okresowo, a inne pojawią się tylko raz.

Jeffery zastanawia się, czy możesz pomóc mu znaleźć pierwsze wystąpienie pewnych trójek, zaczynając od podanych pozycji. Czy możesz mu pomóc?

Wejście

Pierwszy wiersz zawiera dwie liczby całkowite $n$ i $p$ ($1 \le n \le 5000$, $1 \le p \le 2^{30}$), gdzie $n$ oznacza liczbę pytań, a $p$ wskazuje, że wszystkie poniższe pytania są rozpatrywane modulo $p$.

Każdy z następnych $n$ wierszy zawiera cztery liczby całkowite $x$, $y$, $z$ i $m$ ($0 \le x,y,z < p$, $0 \le m \le 10^{18}$), opisujące pytanie o najmniejszą liczbę całkowitą $k$, taką że $k \ge m$ oraz $(a_k,b_k,c_k)\equiv(x,y,z)\pmod p$.

Wyjście

Dla każdego pytania wypisz w osobnym wierszu liczbę całkowitą oznaczającą odpowiedź na to pytanie. Jeśli taka liczba całkowita $k$ nie istnieje, wypisz zamiast niej $-1$.

Przykład

Wejście 1

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

Wyjście 1

11
4
2
-1
0

Wejście 2

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

Wyjście 2

5
-1
6
-1
-1

Uwagi

W pierwszym przykładzie $(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}$ gdzie $T=0,1,2,\ldots$

W drugim przykładzie $(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}$ gdzie $T=0,1,2,\ldots$