Congruences

Problem Description

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 pairwise distinct 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 smallest positive integer $x$ that fulfills all given congruences. If there is no solution exists for the given system of congruences, output $-1$.

Input

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}$.

Output

For each test case, output a single positive integer $x$ representing the answer or output $-1$.

Sample Input

3
2
3 5
2 1
1
13 3
2
3 4
2 4

Sample Output

5
3
4

Hint

You can use __int128 in your C++ code.

Source

2023“钉耙编程”中国大学生算法设计超级联赛（8）