В системе работает k независимых периодических процессов. Для каждого процесса известно, что он срабатывает каждые m_i единиц времени, а первый интересующий нас момент его срабатывания имеет остаток a_i по модулю m_i.

Иначе говоря, для каждого процесса подходят все моменты времени вида: a_i, a_i + m_i, a_i + 2m_i, ...

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

Требуется найти наименьший неотрицательный момент времени x, в который все процессы одновременно находятся в своих требуемых фазах, то есть для каждого i выполняется условие: x при делении на m_i даёт остаток a_i.

Если такого момента не существует, выведите -1.

Заметим, что два процесса с параметрами (a_i, m_i) и (a_j, 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

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

1
0 1

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

0

Пример 2

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

2
1 2
3 5

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

3