Given $m$ equations of the form $a_ix+(x \bmod b_i+1)(x^i \bmod [x^\frac{1}{2}]) \equiv c_i \pmod P,$ where $i$ ranges from $1$ to $m.$ Solve for $x.$

Here, $[x]$ denotes the greatest integer not exceeding $x.$ It is guaranteed that there exists a unique solution between $1$ and $P-1.$

Input

The first line contains an integer $T,$ representing the number of test cases.

For each test case, the first line contains two integers $m$ and $P.$ The next $m$ lines each contain three integers $a_i, b_i,$ and $c_i.$ The symbols have the same meanings as in the problem description.

Output

Output $T$ lines, with one integer between $1$ and $P-1$ per line, representing the answer for each test case.

Examples

Input 1

1
5 233
41 3 13
92 2 86
37 3 222
53 3 85
91 1 80

Output 1

6

Input 2

1
5 10007
3759 3 8193
4694 2 7227
5339 3 5554
8265 3 5493
4167 1 1400

Output 2

106

Input 3

1
5 923097614961380909
400075690252081333 3 65635662366389892
125871709464257940 2 829195963877978233
625686524906165721 3 839495556009110777
240111021937539825 3 718288407067356529
877342215923645363 1 484482855407235702

Output 3

1906

Subtasks

Subtask $1$ ($15\%$): $x \le 10^{12}, b_i=1.$

Subtask $2$ ($10\%$): $x \le 10^{14}, b_i=1.$

Subtask $3$ ($10\%$): $x \le 10^{16}, b_i=1.$

Subtask $4$ ($15\%$): $b_i=1.$

Subtask $5$ ($25\%$): $b_i \le 10.$

Subtask $6$ ($25\%$): $91 \le b_i \le 100.$

For all test cases, $1 \le T \le 40, m=5, 1\le a_i< P, 0\le c_i< P, 9\times 10^{17} \le P \le 10^{18}.$ $P$ is a prime number. All inputs are generated uniformly at random within their respective ranges.

The generation method is as follows: first, $P$ and $x$ are chosen randomly, then for each equation, $a_i$ and $b_i$ are chosen randomly, and the corresponding $c_i$ is generated.