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