Bob 喜欢 Alice。

Alice 和 Bob 想要进行加密通信，于是他们自己设计了一套加密算法进行身份验证。你知道这个加密算法并不可靠，并截获了 Alice 和 Bob 之间的信息。现在你想要恢复出 Alice 的密钥。

Alice 和 Bob 约定了一个大质数 $p$，一个随机范围值 $err$ 和一个在 $0\sim p-1$ 之间均匀随机生成的整数密钥 $x$。其中 $p$ 和 $err$ 的值是公开的，而 $x$ 的值只有 Alice 和 Bob 知道。

当 Bob 想要确认 Alice 的身份时，Bob 会生成 $m$ 个在 $0\sim p-1$ 之间均匀随机生成的 $a_i$ 并发给 Alice。对于每个 $a_i$，Alice 会返回给Bob $a_{i}x$ 模 $p$ 的值。为了防止窃听，Alice 会给结果加上一个在 $-\lceil \frac{err}{2}\rceil$ 到 $\lceil \frac{err}{2}\rceil$ 之间均匀随机生成的扰动。

即，Alice 会返回给 Bob $m$ 组形如 $a_{i}x+b_i\equiv c_i(\mathrm{mod}p)$ 的等式，其中 $b_i$ 为一个不公开的在 $-\lceil \frac{err}{2}\rceil$ 到 $\lceil \frac{err}{2}\rceil$ 之间均匀随机生成的数，$a_i$ 为随机生成的数，$a_i,p,err,c_i$ 为公开的数。

你获得了 Alice 返回的这 $m$ 组等式（即 $m$ 个 $a_i$ 和 $c_i$），你需要求出 $x$ 的值。

输入格式

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

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

输出格式

输出 $T$ 行，对于每组测试数据，输出一个 $0$ 到 $p-1$ 之间整数表示答案。数据保证有解并且解唯一。

样例一

见附加文件中 ex_password1.in 与 ex_password1.ans。

该样例满足题目中提到的所有随机生成的性质。

限制与约定

对于前 $10\mathrm{\%}$ 的数据，满足 $err\le {10}^6$。

对于前 $20\mathrm{\%}$ 的数据，满足 $err\le {10}^8$。

对于前 $30\mathrm{\%}$ 的数据，满足 $err\le {10}^{11}$。

对于前 $40\mathrm{\%}$ 的数据，满足 $err\le {10}^{12}$。

对于另外 $20\mathrm{\%}$ 的数据，满足 $p\le {10}^{16},m=2000$。

对于 $100\mathrm{\%}$ 的数据，满足 ${10}^{15}\le p\le {10}^{18},50\le m\le 2000,1\le err\le 0.01p,1\le T\le 5,0\le a_i,c_i\le p-1$，保证 $p$ 为素数。

时间限制：$1\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

下载

样例数据下载