Jeffery menemukan sebuah barisan tripel yang menakjubkan $\{(a_k,b_k,c_k)\}_{k=0}^{\infty}$:

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

• untuk setiap bilangan bulat tak negatif $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)$.

Sebagai contoh, $(a_1,b_1,c_1)=(5,2,1)$ dan $(a_2,b_2,c_2)=(29,12,5)$.

Jika kita mempertimbangkan barisan ini modulo suatu bilangan bulat $p$, beberapa tripel tidak akan pernah muncul dalam barisan ini, beberapa akan muncul secara periodik, dan tripel lainnya hanya akan muncul sekali.

Jeffery ingin tahu apakah kamu dapat membantunya menemukan kemunculan pertama beberapa tripel, dimulai dari posisi yang diberikan. Bisakah kamu membantunya?

Masukan

Baris pertama berisi dua bilangan bulat $n$ dan $p$ ($1 \le n \le 5000$, $1 \le p \le 2^{30}$), di mana $n$ menyatakan jumlah pertanyaan dan $p$ menunjukkan bahwa semua pertanyaan berikut dipertimbangkan modulo $p$.

Setiap baris dari $n$ baris berikutnya berisi empat bilangan bulat $x$, $y$, $z$ dan $m$ ($0 \le x,y,z < p$, $0 \le m \le 10^{18}$) yang mewakili pertanyaan untuk mencari bilangan bulat terkecil $k$ sehingga $k \ge m$ dan $(a_k,b_k,c_k)\equiv(x,y,z)\pmod p$.

Keluaran

Untuk setiap pertanyaan, cetak sebuah bilangan bulat dalam satu baris, yang menyatakan jawaban pertanyaan tersebut. Jika tidak ada bilangan bulat $k$ seperti itu, cetak $-1$ sebagai gantinya.

Contoh

Masukan 1

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

Keluaran 1

11
4
2
-1
0

Masukan 2

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

Keluaran 2

5
-1
6
-1
-1

Catatan

Pada contoh pertama, $(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}$ di mana $T=0,1,2,\ldots$

Pada contoh kedua, $(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}$ di mana $T=0,1,2,\ldots$