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

Ràng buộc & Subtasks