Легендарные персонажи математических задач Алиса и Боб столько раз вместе сыграли в различные игры, что между ними не могла не пробежать искорка симпатии, которую ветер времени вскоре раздул в огонь любви. И вот уже который год они живут вместе и продолжают искать новые оптимальные стратегии. Иногда в их жизни происходят довольно прозаичные события, и эта задача поведает вам об одном из них.

Однажды Боб, пересчитав деньги в семейном бюджете, обнаружил недостачу 10¹² денежных единиц. Он подумал, что часть этой суммы могла потратить Алиса. Когда она пришла домой в новом платье и туфлях (что только усилило подозрения Боба), он спросил у неё, сколько денег она взяла из семейного бюджета. Алиса не сказала сумму прямо, но предложила Бобу сыграть в игру, в ходе которой он сможет узнать искомое число. Конечно же, Боб не смог устоять.

Вот правила этой игры. У Алисы есть целое число x (1 ≤ x ≤ 10¹²). Игра состоит из n ходов. На каждом ходу Боб спрашивает Алису, делится ли число x на некоторое целое положительное число d_i. Затем Алиса отвечает на вопрос Боба. После этого Боб должен назвать любое возможное целое число x'_i (1 ≤ x'_i ≤ 10¹²), которое удовлетворяет всей полученной информации (включая информацию, полученную на предыдущих ходах), либо сказать, что такого x'_i не существует.

Боб сам выбрал, какие вопросы он будет задавать, но вот задача определения возможного числа x'_i после каждого хода для него слишком сложна. Поможете Бобу вывести Алису на чистую воду?

В первой строке дано целое число n — количество ходов (1 ≤ n ≤ 10⁵).

В следующих n строках дано описание ходов. Каждый ход описывается целыми числами d_i и t_i (1 ≤ d_i ≤ 10⁶; t_i ∈ {0, 1}). В случае утвердительного ответа Алисы t_i = 1, а в случае отрицательного t_i = 0.

Выведите n строк, описывающих ответы Боба на каждом ходу. Каждая строка должна содержать либо число x'_i (1 ≤ x'_i ≤ 10¹²), либо -1, если подходящего x'_i не существует.