Jeffery found an amazing sequence of triples $\{(a_k,b_k,c_k)\}_{k=0}^{\infty}$:

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

• for each non-negative integer $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)$.

For example, $(a_1,b_1,c_1)=(5,2,1)$ and $(a_2,b_2,c_2)=(29,12,5)$.

If we consider the sequence in modulo an integer $p$, some triples would never appear in this sequence, some triples would appear periodically and other triples would appear only once.

Jeffery is wondering if you could help him find out the first appearance of some triples starting from given positions. Could you help him, please?

Input

The first line contains two integers $n$ and $p$ ($1 \le n \le 5000$, $1 \le p \le 2^{30}$) where $n$ indicates the number of questions and $p$ indicates all the following questions are considered in modulo $p$.

Each of the next $n$ lines contains four integers $x$, $y$, $z$ and $m$ ($0 \le x,y,z < p$, $0 \le m \le 10^{18}$) representing a question that queries you to find the minimum integer $k$ such that $k \ge m$ and $(a_k,b_k,c_k)\equiv(x,y,z)\pmod p$.

Output

For each question, output an integer in a single line, indicating the answer to the question. If there is no such integer $k$, output $-1$ instead.

Examples

Input 1

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

Output 1

11
4
2
-1
0

Input 2

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

Output 2

5
-1
6
-1
-1

Note

In the first sample, $(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}$ where $T=0,1,2,\ldots$

In the second sample, $(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}$ where $T=0,1,2,\ldots$