Bob likes Alice.

Alice and Bob want to communicate securely, so they designed an encryption algorithm for authentication. You know this encryption algorithm is unreliable and have intercepted the information between Alice and Bob. Now you want to recover Alice's secret key.

Alice and Bob have agreed on a large prime $p$, a random range value $err$, and a secret key $x$ uniformly and randomly generated between $0$ and $p-1$. The values of $p$ and $err$ are public, while the value of $x$ is known only to Alice and Bob.

When Bob wants to verify Alice's identity, Bob generates $m$ values $a_i$, each uniformly and randomly generated between $0$ and $p-1$, and sends them to Alice. For each $a_i$, Alice returns the value of $a_i x \pmod p$ to Bob. To prevent eavesdropping, Alice adds a perturbation to the result, which is uniformly and randomly generated between $-\lceil \frac{err}{2} \rceil$ and $\lceil \frac{err}{2} \rceil$.

That is, Alice returns to Bob $m$ equations of the form $a_i x + b \equiv c_i \pmod p$, where $b$ is a private number uniformly and randomly generated between $-\lceil \frac{err}{2} \rceil$ and $\lceil \frac{err}{2} \rceil$, $a_i$ are the randomly generated numbers, and $a_i, p, err, c_i$ are public numbers.

You have obtained these $m$ equations (i.e., $m$ pairs of $a_i$ and $c_i$) returned by Alice, and you need to find the value of $x$.

Input

The first line contains an integer $T$, representing the number of test cases.

For each test case, the first line contains three integers $m, p, err$. The next $m$ lines each contain two integers $a_i, c_i$. The meanings of the symbols are the same as in the problem description.

Output

Output $T$ lines. For each test case, output an integer between $0$ and $p-1$ representing the answer. It is guaranteed that a solution exists and is unique.

Examples

Input 1

(See external file)

Output 1

(See external file)

Constraints

• For the first 10% of the data, $err \le 10^6$.
• For the first 20% of the data, $err \le 10^8$.
• For the first 30% of the data, $err \le 10^{11}$.
• For the first 40% of the data, $err \le 10^{12}$.
• For another 20% of the data, $p \le 10^{16}, m = 2000$.
• For 100% of the data, $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$, and $p$ is guaranteed to be a prime.

Note

The final evaluation environment does not support __int128. If necessary, please implement 128-bit integers manually; you are responsible for any compilation errors caused by this.