Một người đàn ông có một số trứng gà. Khi đếm theo từng chục (10 quả) thì dư \(r_1\) quả. Khi đếm theo tá (12 quả) thì dư \(r_2\) quả. Khi đếm theo thùng (20 quả) thì dư \(r_3\) quả. Hỏi số trứng ít nhất là bao nhiêu? Bài toán tổng quát: tìm \(x\) nhỏ nhất thỏa hệ phương trình đồng dư: \(x \equiv r_i \pmod{m_i}\).

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

• Dòng đầu: số nguyên \(n\) (\(2 \le n \le 10\)).
• \(n\) dòng tiếp, dòng thứ \(i\) chứa hai số \(m_i, r_i\) (\(1 \le m_i \le 10^9\), \(0 \le r_i < m_i\)).
• Tất cả \(m_i\) đôi một nguyên tố cùng nhau.

Định dạng đầu ra

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

Ví dụ

Input:

3
3 2
5 3
7 2

Output:

23

Giải thích: \(23 \equiv 2 \pmod{3}\), \(23 \equiv 3 \pmod{5}\), \(23 \equiv 2 \pmod{7}\).

Ràng buộc

• 100% số điểm: \(m_i \le 10^9\), các \(m_i\) đôi một nguyên tố cùng nhau.