Jeffery a découvert une étonnante suite de triplets $\{(a_k,b_k,c_k)\}_{k=0}^{\infty}$ :

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

• pour chaque entier non négatif $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)$.

Par exemple, $(a_1,b_1,c_1)=(5,2,1)$ et $(a_2,b_2,c_2)=(29,12,5)$.

Si l'on considère la suite modulo un entier $p$, certains triplets n'apparaîtront jamais dans cette suite, certains apparaîtront périodiquement et d'autres n'apparaîtront qu'une seule fois.

Jeffery se demande si vous pourriez l'aider à trouver la première apparition de certains triplets à partir de positions données. Pourriez-vous l'aider, s'il vous plaît ?

Entrée

La première ligne contient deux entiers $n$ et $p$ ($1 \le n \le 5000$, $1 \le p \le 2^{30}$), où $n$ indique le nombre de questions et $p$ indique que toutes les questions suivantes sont considérées modulo $p$.

Chacune des $n$ lignes suivantes contient quatre entiers $x$, $y$, $z$ et $m$ ($0 \le x,y,z < p$, $0 \le m \le 10^{18}$), représentant une question qui vous demande de trouver le plus petit entier $k$ tel que $k \ge m$ et $(a_k,b_k,c_k)\equiv(x,y,z)\pmod p$.

Sortie

Pour chaque question, affichez un entier sur une ligne, indiquant la réponse à la question. S'il n'existe pas de tel entier $k$, affichez $-1$ à la place.

Exemples

Entrée 1

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

Sortie 1

11
4
2
-1
0

Entrée 2

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

Sortie 2

5
-1
6
-1
-1

Remarque

Dans le premier exemple, $(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}$ où $T=0,1,2,\ldots$

Dans le second exemple, $(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}$ où $T=0,1,2,\ldots$