Legendary characters of mathematical problems Alice and Bob played together so often and in so many games that there was no avoiding a flicker of sympathy between them, which was then kindled into flame of love by the wind of time. Nowadays they have been living together for some years and searching for the new strategies. Sometimes in their life there are some prosaic events, and this problem will tell you about one of them.

Once Bob counted the money of the family budget and found a shortage of 10¹² conventional units. He thought that part of it could be spent by Alice. When she came home in a new dress and shoes (which only increased Bob’s suspicions), he asked her how much money she took from the family budget. Alice did not say the amount directly, but suggested Bob to play a game, during which he would be able to find out the required number. Of course, Bob could not resist.

Here are the rules of this game. Alice has an integer x (1 ≤ x ≤ 10¹²). The game consists of n moves. On each move Bob asks Alice if the number x is divided by some positive integer d_i. Then Alice answers Bob’s question. After that Bob should suggest any possible integer x'_i (1 ≤ x'_i ≤ 10¹²), which satisfies all the information received (including information obtained from the previous moves), or say that such x'_i does not exist.

Bob himself chose what questions he would ask, but the task of determining the possible number x'_i after each move is too difficult for him. Help Bob to do it.

The first line contains an integer n that is the number of moves (1 ≤ n ≤ 10⁵).

In following n lines there is a description of the moves. Each move is described by integers d_i and t_i (1 ≤ d_i ≤ 10⁶; t_i ∈ {0, 1}). If the Alice’s answer is positive, then t_i equals 1. If the answer is negative, then t_i equals 0.

Output n lines that describe Bob’s answers on each move. Each line must contain either integer x'_i (1 ≤ x'_i ≤ 10¹²) or -1 if there is no suitable x'_i.