问题 C: Congruences

Your task is to solve a system of m congruences, each one represented in the following format: x pi ≡ qi (mod n) (i = 1, 2, ..., m) Here, pi refers to pairwise distinct prime numbers, n is the product of all pi (i.e., n = Qm i=1 pi), and qi 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.

The first line contains a positive integer T (1 ≤ T ≤ 104 ), 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 pi and qi (2 ≤ pi ≤ 1018 , 0 ≤ qi < n). It is guaranteed that n = Qm i=1 pi ≤ 1018 . 

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

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

5
3
4