题目描述

有 $T$ 个不超过 $10^{18}$ 的正整数 $x$，知道这个数除以若干个数的余数，求这个正整数最小是多少。

输入描述

第一行是一个整数 $T$，代表需要你计算的正整数个数。

每个测试数据的第一行是一个整数 $n$ 表示有 $n$ 个除数及对应余数。接下来 $n$ 行每行两个数 $m_i,a_i$，代表这个正整数除以 $m_i$ 的余数为 $a_i$。

输出描述

对每个输入输出一个整数表示答案。

3
3
7 2
5 3
11 4
3
4 2
5 3
6 4
1
100 3

268
58
3

评测用例规模与约定：

$1≤T≤10^5$，$1≤n≤15$，$0≤a_i<m_i≤10^9$。

单个测试点 $\sum n≤10^6$。

保证 $lcm(a_1,a_2,...a_n)≤10^{18}$。