Общий элемент

Напишите программу, которая определит наименьшее натуральное число, принадлежащее одновременно всем заданным n бесконечным арифметическим прогрессиям натуральных чисел.

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

Входные данные содержат (2n + 1) неотрицательное целое число. Первым идет число n (n < 100). Каждая из следующих n пар чисел представляет собой первый член j-й прогрессии и ее разность. Все числа не превышают 10000.

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

Выведите искомое число. Если такого числа не существует, выведите 0.

Примеры