给定 $m$ 个如下形式的方程：

$$a_i \cdot x + err_i \equiv c_i \pmod p$$

其中 $err_i$ 是一个未知的随机误差项，从 $-\lfloor \frac{p}{200} \rfloor, \dots, \lfloor \frac{p}{200} \rfloor$ 中均匀随机选择，而 $a_i, c_i$ 和 $p$ 是已知的。

已知这些方程对于某个未知的整数 $x$ 成立。请找到其中一个 $x$。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 500$)，表示测试用例的数量。每个测试用例的格式如下：

• 第一行包含 $m, p$ ($50 \le m \le 100, 10^{15} \le p \le 10^{18}$)。
• 接下来的 $m$ 行，每行包含 $a_i, c_i$ ($0 \le a_i, c_i \le p - 1$)。
• 保证 $p$ 是一个素数，$a_i, x$ 从 $0$ 到 $p-1$ 中均匀随机选择，$c_i$ 由 $(a_i \cdot x + err_i) \pmod p$ 计算得出，$err_i$ 是从 $-\lfloor \frac{p}{200} \rfloor, \dots, \lfloor \frac{p}{200} \rfloor$ 中均匀随机选择的整数。

输出格式

对于每个测试用例，输出一个整数，即答案。如果存在多个解，输出任意一个即可。

样例

输入 1

1
50 922033901407246477
492300877907148697 8585039545574817
36478175140515505 237143454432095134
537753813197233578 694568987600933631
...
(truncated)

输出 1

578607642570710976

说明

完整的样例测试用例可在比赛系统中获取。