给定 T 组同余方程组，每组包含 n 条形如
x \equiv a_i \pmod{m_i}
的方程。请求出满足所有方程的最小非负整数解 x （即 0 \le x < L ，其中 L = \operatorname{lcm}(m_1, \dots, m_n) ）。若方程组无解，输出 -1 。
第一行一个整数 T 。
对每个测试用例：第一行一个整数 n ，接下来 n 行每行两个整数 a_i, m_i （ 0 \le a_i < m_i ）。
输出 T 行，每行一个整数（最小非负解，或 -1 ）。
3 2 1 2 0 3 2 4 5 2 7 3 1 6 2 10 3 15
3 9 -1
对于全部数据： 1 \le T \le 10^5 ， 1 \le n \le 100 ， 0 \le a_i < m_i \le 10^{18} 。
用两两合并的方式增量求解：维护当前解 (x, M) 与新方程 (a, m) ，先用扩展欧几里得求 g = \gcd(M, m) ；若 x \bmod g \ne a \bmod g 则无解，否则合并为 (x + M \cdot t,\ \mathrm{lcm}(M, m)) 。当 m_i 接近 10^{18} 时，乘积与合并步都需要 __int128 防止溢出。
__int128