وجد 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$