中国剩余定理

题目描述

一共$T$组数据，每组数据，给定$n$个方程，求$x\equiv a_i \pmod{m_i}$。

输入格式

第一行一个整数$T$。

接下来对于每组数据，第一行一个整数$n$，接下来$n$行，每行两个整数$a_i, m_i$。

输出格式

对于每组数据，一个整数，表示答案，答案一定要在$0$到$\mathrm{lcm} (m_1, m_2, \dots, m_n)-1$之间，数据保证有解。

样例输入

1
3
1 10
2 11
3 12

样例输出

651

数据范围

保证$T\leq 1000, n\leq 10, 0\leq a_i < m_i \leq 10^9$，保证$\mathrm{lcm} (m_1, m_2, \dots, m_n)$不超过$10^{18}$。