Jeffery tìm thấy một dãy bộ ba kỳ diệu $\{(a_k,b_k,c_k)\}_{k=0}^{\infty}$:

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

• với mỗi số nguyên không âm $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)$.

Ví dụ, $(a_1,b_1,c_1)=(5,2,1)$ và $(a_2,b_2,c_2)=(29,12,5)$.

Nếu xét dãy theo môđun một số nguyên $p$, một số bộ ba sẽ không bao giờ xuất hiện trong dãy này, một số bộ ba sẽ xuất hiện tuần hoàn, còn những bộ ba khác chỉ xuất hiện một lần.

Jeffery muốn biết liệu bạn có thể giúp cậu ấy tìm lần xuất hiện đầu tiên của một số bộ ba, bắt đầu từ các vị trí cho trước hay không. Bạn có thể giúp cậu ấy không?

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $p$ ($1 \le n \le 5000$, $1 \le p \le 2^{30}$), trong đó $n$ là số câu hỏi và $p$ cho biết tất cả các câu hỏi sau được xét theo môđun $p$.

Mỗi dòng trong $n$ dòng tiếp theo chứa bốn số nguyên $x$, $y$, $z$ và $m$ ($0 \le x,y,z < p$, $0 \le m \le 10^{18}$), biểu diễn một câu hỏi yêu cầu bạn tìm số nguyên $k$ nhỏ nhất sao cho $k \ge m$ và $(a_k,b_k,c_k)\equiv(x,y,z)\pmod p$.

Dữ liệu ra

Với mỗi câu hỏi, in một số nguyên trên một dòng riêng biểu thị đáp án cho câu hỏi đó. Nếu không tồn tại số nguyên $k$ như vậy, hãy in $-1$ thay thế.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

11
4
2
-1
0

Dữ liệu vào 2

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

Dữ liệu ra 2

5
-1
6
-1
-1

Ghi chú

Trong ví dụ thứ nhất, $(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}$ trong đó $T=0,1,2,\ldots$

Trong ví dụ thứ hai, $(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}$ trong đó $T=0,1,2,\ldots$