ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

2130. Alice + Bob

Time limit: 2.5 second
Memory limit: 256 MB
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 1012 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 ≤ 1012). The game consists of n moves. On each move Bob asks Alice if the number x is divided by some positive integer di. Then Alice answers Bob’s question. After that Bob should suggest any possible integer x'i (1 ≤ x'i ≤ 1012), 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.

Input

The first line contains an integer n that is the number of moves (1 ≤ n ≤ 105).
In following n lines there is a description of the moves. Each move is described by integers di and ti (1 ≤ di ≤ 106; ti ∈ {0, 1}). If the Alice’s answer is positive, then ti equals 1. If the answer is negative, then ti equals 0.

Output

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

Samples

inputoutput
3
10 1
5 0
100500 0
100500
-1
-1
6
2 1
5 0
3 1
1 1
5 1
100500 0
12
12
12
12
-1
-1
6
1000000 1
999999 1
2 0
999998 1
999997 1
999996 1
999999000000
999999000000
-1
-1
-1
-1
Problem Author: Kirill Borozdin and Nikita Sivukhin, prepared by Vladimir Leskov
Problem Source: "Later is better than never" Contest