Several orbital gears each return to a marked slot on their own cycle. Gear i is aligned exactly when the step counter t satisfies t = r_i (mod m_i). The moduli are pairwise coprime. Find the smallest non-negative step count t at which every gear is simultaneously aligned. Such a t always exists and is unique modulo the product of the moduli.
Input format
Line 1: an integer k, the number of gears.
Next k lines: two integers r_i and m_i with 0 <= r_i < m_i.
Output format
A single integer: the smallest non-negative t with t = r_i (mod m_i) for all i.
Constraints
- 1 <= k <= 10
- 1 <= m_i <= 1000
- The moduli are pairwise coprime.