Time Limit: 3.0 s

Memory Limit: 64.0 MB

Description

Lets define LCD as lowest common divisor (greater than 1) of any two number.
You are given two positive number n and m. find the LCD of n and m.
or report that there are no LCD between n and m.
for example : LCD of 20 and 50 is 2 ( 2 is the lowest number(LCD != 1) which is the divisor of both 20 and 50)

Input

First line will contain an integer T : number of testcases
each of next T lines will contain two positive integers n,m ;

1<= T <= \(10^4\)
1<= N,M <= \(10^6\)

Output

print T lines , each line should contain an integer, the LCD of n and m.
if there is no LCD print -1

Sample

3
4 8
1 10
3 9

2
-1
3