Giải hệ phương trình đồng dư với số lượng phương trình lớn (\(k \le 100\)). Các \(m_i\) đôi một nguyên tố cùng nhau.

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

• Dòng đầu: số nguyên \(k\) (\(2 \le k \le 100\)).
• \(k\) dòng tiếp: mỗi dòng \(a_i, m_i\) (\(0 \le a_i < m_i \le 10^6\), 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:

4
0 2
0 3
1 5
0 7

Output:

15

Ràng buộc

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