题目描述

农场主老张养了一群羊，但他记不清具体有多少只。为了弄清数目，他让助手小李帮忙统计。小李发现，如果把羊分成若干圈，每圈大小不同，总会有若干只羊没有合适的圈可以待。

举个例子，假如有 $16$ 只羊，如果建了 $3$ 个圈，会剩下 $1$ 只羊没地方去。如果建了 $5$ 个圈，同样会剩下 $1$ 只羊没地方去。如果建了 $7$ 个圈，会剩下 $2$ 只羊没地方去。

你作为老张的会计，需要准确算出他至少养了多少只羊。

输入格式

第一行包含一个整数 $n$，表示统计的次数。

接下来 $n$ 行，每行两个整数 $a_i, b_i$，表示分成 $a_i$ 个圈时，有 $b_i$ 只羊没有去处。

你可以假定 $a_1 \sim a_n$ 两两互质。

输出格式

输出一个自然数，即为至少养羊的数目。

样例

3
3 1
5 1
7 2

16

提示

$1 \leq n \leq 10$，$0 \leq b_i \lt a_i \leq 100000$，$1 \leq \prod a_i \leq 10^{18}$

答案不唯一，输出最小的满足条件的正整数即可。

本题为中国剩余定理（CRT）的模板题。