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$ כך ש-$k \ge m$ וגם $(a_k,b_k,c_k)\equiv(x,y,z)\pmod p$.

פלט

לכל שאלה, הדפיסו מספר שלם בשורה אחת המציין את התשובה לשאלה. אם אין מספר שלם $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$