题目描述
Your task is to solve a system of $m$ congruences, each one represented in the following format:
$$
x ^ {p_i} \equiv q_i \pmod n \quad (i = 1, 2, ..., m)
$$
Here, $p_i$ refers to [b]pairwise distinct[/b] prime numbers, $n$ is the product of all $p_i$ (i.e., $n = \prod_{i=1}^{m} p_i$), and $q_i$ is an integer within the range of $[0, n)$.
The goal is to find the [b]smallest positive[/b] integer $x$ that fulfills all given congruences. If there is no solution exists for the given system of congruences, output $-1$.
$$
x ^ {p_i} \equiv q_i \pmod n \quad (i = 1, 2, ..., m)
$$
Here, $p_i$ refers to [b]pairwise distinct[/b] prime numbers, $n$ is the product of all $p_i$ (i.e., $n = \prod_{i=1}^{m} p_i$), and $q_i$ is an integer within the range of $[0, n)$.
The goal is to find the [b]smallest positive[/b] integer $x$ that fulfills all given congruences. If there is no solution exists for the given system of congruences, output $-1$.
输入
The first line contains a positive integer $T$ ($1 \le T \le 10^4$), indicating the number of test cases.
For each test case, the first line contains a positive integer $m$, and each of the following $m$ lines contains two integers $p_i$ and $q_i$ ($2\le p_i\le 10^{18}$, $0\le q_i < n$). It is guaranteed that $n = \prod_{i=1}^{m} p_i \le 10^{18}$.
For each test case, the first line contains a positive integer $m$, and each of the following $m$ lines contains two integers $p_i$ and $q_i$ ($2\le p_i\le 10^{18}$, $0\le q_i < n$). It is guaranteed that $n = \prod_{i=1}^{m} p_i \le 10^{18}$.
输出
For each test case, output a single positive integer $x$ representing the answer or output $-1$.
样例输入 Copy
3
2
3 5
2 1
1
13 3
2
3 4
2 4
样例输出 Copy
5
3
4