C. Cryptography Problem
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given $$$m$$$ equations of the form $$$$$$a_i \cdot x + err_i \equiv c_i \pmod p.$$$$$$ Here, $$$err_i$$$ is an unknown random error term, chosen uniformly at random from $$$-\lfloor \frac{p}{200} \rfloor, \ldots, \lfloor \frac{p}{200} \rfloor$$$, while $$$a_i, c_i$$$ and $$$p$$$ are known to you.

You know that these equations hold for some unknown integer $$$x$$$. Find one such $$$x$$$.

Input

In the first line, $$$T$$$ ($$$1\leq T\leq 500$$$) — the number of test cases. For each test case:

  • In the first line, $$$m, p$$$ ($$$50\leq m\leq 100, 10^{15} \leq p \leq 10^{18}$$$).
  • In the next $$$m$$$ lines, $$$a_i, c_i$$$ ($$$0\leq a_i, c_i\leq p - 1$$$).
  • It's guaranteed that $$$p$$$ is a prime, $$$a_i, x$$$ are chosen uniformly at random from $$$0$$$ to $$$p - 1$$$, and $$$c_i$$$ is computed by $$$(a_i \cdot x + err_i) \bmod p$$$, $$$err_i$$$ is an integer chosen uniformly at random from $$$-\lfloor \frac{p}{200} \rfloor, \ldots, \lfloor \frac{p}{200} \rfloor$$$.
Output

For each test case, one integer — the answer. If there are multiple solutions, you may output any.

Example
Input
1
50 922033901407246477
492300877907148697 8585039545574817
36478175140515505 237143454432095134
537753813197233578 694568987600933631
...
(truncated)
Output
578607642570710976
Note

The full sample test case is available in the contest system.