Arun has two positive integers P and Q and he wants to compute Terrafactor of P and Q.Terrafactor R of P and Q is the maximum number which has the following two properties.

 i. P%R=0

ii. gcd(Q,R)=1

Help Arun find the Terrafactor of pair of integers.

INPUT:

T be test Cases.Following T lines has pair P and Q.

1<=T<=10⁶

1<=P,Q<=10⁶