Chinese Remainder Theorem

Problem Description

There are $T$ test cases. For each case you are given $n$ equations and must find $x$ such that $x \equiv a_i \pmod{m_i}$ for every $i$.

Input Format

The first line contains an integer $T$.

For each test case, the first line contains an integer $n$, and the following $n$ lines each contain two integers $a_i, m_i$.

Output Format

For each test case, output one integer: the answer. The answer must lie in the range $0$ to $\mathrm{lcm}(m_1, m_2, \dots, m_n) - 1$. The data guarantees that a solution exists.

Sample Input

1
3
1 10
2 11
3 12

Sample Output

651

Constraints

$T \leq 1000$, $n \leq 10$, $0 \leq a_i < m_i \leq 10^9$. It is guaranteed that $\mathrm{lcm}(m_1, m_2, \dots, m_n)$ does not exceed $10^{18}$.