Cho hệ phương trình đồng dư với \(k\) phương trình. Các \(m_i\) đôi một nguyên tố cùng nhau. Hãy tìm nghiệm bằng thuật toán Garner (xây dựng từng bước).

Đị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 \(a_i, m_i\).

Đị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}\).