В распределённой системе согласования хранится k условий на глобальный идентификатор x.

i-е условие задаётся парой чисел a_i и m_i и означает, что идентификатор должен иметь остаток a_i при делении на m_i, то есть:

x ≡ a_i (mod m_i)

Модули m_i могут быть любыми положительными целыми числами и не обязаны быть попарно взаимно простыми.

Требуется определить, можно ли одновременно согласовать все условия. Если можно, найдите наименьший неотрицательный идентификатор x, удовлетворяющий всем условиям. Если нельзя, выведите -1.

Известно, что два условия x ≡ a_i (mod m_i) и x ≡ a_j (mod m_j) совместимы тогда и только тогда, когда разность a_i - a_j делится на gcd(m_i, m_j). Если вся система совместна, то общее решение существует и единственно по модулю lcm(m_1, ..., m_k).

Входные данные

В первой строке задано целое число k — количество условий.

В следующих k строках задано по два целых числа a_i и m_i.

Выходные данные

Если система имеет решение, выведите наименьшее целое неотрицательное x, удовлетворяющее всем условиям.

Иначе выведите -1.

Ограничения

• 1 <= k <= 100
• 1 <= m_i <= 10^9
• 0 <= a_i < m_i
• гарантируется, что lcm(m_1, ..., m_k) <= 10^18

Примеры

Пример 1

Входные данные

3
1 2
3 4
5 6

Выходные данные

11

Пример 2

Входные данные

2
0 2
1 4

Выходные данные

-1