G. Baby Ehab and a GCD Problem, Of Course
time limit per test
1 second
memory limit per test
256 megabytes
input
gcd.in
output
standard output

Ehab the baby was playing with special cubes that had numbers written on them.

Every while, Baby Badawy, who envied Ehab for being younger than him, would throw all the cubes with numbers between a pair of numbers ($$$l$$$ and $$$r$$$) he chose on Baby Ehab.

Every time Badawy threw cubes on Ehab, Ehab would just add them to his cubes, calculate the $$$GCD$$$ of the numbers written on all of the cubes he has so far, and write the result on a piece of paper.

Note that the $$$GCD$$$ of a sequence of numbers is the greatest number that divides all of them.

Can you guess the numbers Ehab wrote knowing which cubes Badawy threw each time?

Input

The first line contains a single integer $$$q$$$ $$$(1 \leq q \leq 10 ^ 5)$$$ — the number of times Badawy threw cubes on Ehab.

Each of the following $$$q$$$ lines will contain two integers $$$l_i$$$ and $$$r_i$$$ $$$(1 \leq l_i \leq r_i \leq 10 ^{18})$$$ — meaning that for each number between $$$l_i$$$ and $$$r_i$$$ (inclusive), Badawy will throw a cube on Ehab with that number written on it.

Output

Output $$$q$$$ integers each on a single line — the numbers that Ehab wrote down.

Example
Input
4
2250 2250
126 126
1 6
6 8
Output
2250
18
1
1