Cho hệ phương trình đồng dư bậc nhất: \(x \equiv a_i \pmod{m_i}\) với \(i = 1 \dots k\).

Trong đó các số \(m_i\) nguyên tố cùng nhau đôi một (\(\gcd(m_i, m_j) = 1\) với \(i \neq j\)). Hãy tìm nghiệm \(x\) không âm nhỏ nhất thỏa mãn hệ phương trình trên.

Dữ liệu vào

• Dòng đầu chứa số nguyên \(k\) (\(1 \le k \le 10\)).
• \(k\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(a_i\) và \(m_i\) (\(0 \le a_i < m_i \le 10^9\)). Tích \(M = m_1 \cdot m_2 \dots m_k \le 10^{18}\).

Dữ liệu ra

• In ra một số nguyên duy nhất là nghiệm \(x\) không âm nhỏ nhất (\(0 \le x < M\)) thỏa mãn hệ phương trình.

Ví dụ

Đầu vào:

3
2 3
3 5
2 7

Đầu ra:

23