给 $m$ 个方程，形如 $a_ix+(x \bmod b_i+1)(x^i \bmod [x^\frac{1}{2}]) \equiv c_i \pmod P.$ 其中 $i$ 从 $1$ 到 $m.$ 求解 $x.$

其中 $[x]$ 表示最大不超过 $x$ 的整数。数据保证在 $1$ 和 $P-1$ 之间有且仅有唯一解.

Input

第一行输入一个整数 $T$，表示数据组数.

对于每组数据，第一行输入两个个整数 $m,P$。接下来 $m$ 行，每行三个整数 $a_i,b_i,c_i.$ 符号的含义和题面中相同.

Output

输出 $T$ 行，每组测试数据一行，输出一个 $1$ 到 $P−1$ 之间整数表示答案.

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

Scoring

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.$

对于所有测试数据，满足 $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$ 是素数。所有输入在对应数据范围内均匀随机生成.

下面给出具体生成方式：先随机 $P,x,$ 再对每一个方程随机 $a_i,b_i,$ 生成对应的 $c_i.$