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$