Jeffery hat eine erstaunliche Folge von Tripeln $\{(a_k,b_k,c_k)\}_{k=0}^{\infty}$ gefunden:

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

• für jede nichtnegative ganze Zahl $k$ gilt $(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)$.

Zum Beispiel sind $(a_1,b_1,c_1)=(5,2,1)$ und $(a_2,b_2,c_2)=(29,12,5)$.

Wenn wir die Folge modulo einer ganzen Zahl $p$ betrachten, kommen einige Tripel niemals in dieser Folge vor, einige erscheinen periodisch und andere nur ein einziges Mal.

Jeffery fragt sich, ob du ihm helfen kannst, das erste Auftreten einiger Tripel ab gegebenen Positionen zu finden. Könntest du ihm bitte helfen?

Eingabe

Die erste Zeile enthält zwei ganze Zahlen $n$ und $p$ ($1 \le n \le 5000$, $1 \le p \le 2^{30}$), wobei $n$ die Anzahl der Fragen angibt und $p$ angibt, dass alle folgenden Fragen modulo $p$ betrachtet werden.

Jede der nächsten $n$ Zeilen enthält vier ganze Zahlen $x$, $y$, $z$ und $m$ ($0 \le x,y,z < p$, $0 \le m \le 10^{18}$). Sie beschreibt eine Frage, bei der du die kleinste ganze Zahl $k$ mit $k \ge m$ und $(a_k,b_k,c_k)\equiv(x,y,z)\pmod p$ finden sollst.

Ausgabe

Gib für jede Frage eine ganze Zahl in einer eigenen Zeile aus, die die Antwort auf die Frage angibt. Falls es keine solche ganze Zahl $k$ gibt, gib stattdessen $-1$ aus.

Beispiele

Eingabe 1

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

Ausgabe 1

11
4
2
-1
0

Eingabe 2

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

Ausgabe 2

5
-1
6
-1
-1

Hinweis

Im ersten Beispiel gilt $(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}$ wobei $T=0,1,2,\ldots$

Im zweiten Beispiel gilt $(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}$ wobei $T=0,1,2,\ldots$