提高-⏱ 1000ms💾 256MB#P7059

题目描述

两两互质模数的同余方程组 x≡rᵢ(mod mᵢ),求最小非负解。

输入格式

第一行整数 k(1..3);接下来 k 行每行两个整数 rᵢ mᵢ(模数两两互质,乘积 ≤ 1e18)。

输出格式

一行一个整数。

数据范围

$$0 \le r_i < m_i \le 10^9$$

样例输入 #1
1
3 5
样例输出 #1
3
样例输入 #2
2
2 3
3 5
样例输出 #2
8