Cho hệ phương trình đồng dư: \(x \equiv a_1 \pmod{m_1}\) \(x \equiv a_2 \pmod{m_2}\) ... \(x \equiv a_k \pmod{m_k}\)

Các \(m_i\) đôi một nguyên tố cùng nhau. Tìm nghiệm không âm nhỏ nhất.

Định dạng đầu vào

• Dòng đầu: số nguyên \(k\) (\(2 \le k \le 10\)).
• \(k\) dòng tiếp: mỗi dòng gồm \(a_i, m_i\) (\(0 \le a_i < m_i \le 10^9\), các \(m_i\) đôi một nguyên tố cùng nhau, tích \(M \le 10^{18}\)).

Định dạng đầu ra

• Một số nguyên là nghiệm không âm nhỏ nhất.

Ví dụ

Input:

3
2 3
3 5
2 7

Output:

23

Ràng buộc

• 100% số điểm: \(M \le 10^{18}\).