Oleg's favorite subjects are History and Math, and his favorite branch of mathematics is division.

To improve his division skills, Oleg came up with t pairs of integers p_i and q_i and for each pair decided to find the greatest integer x_i, such that: 

  * p_i is divisible by x_i; 
  * x_i is not divisible by q_i. 

Oleg is really good at division and managed to find all the answers quickly, how about you?

Input

The first line contains an integer t (1 ≤ t ≤ 50) — the number of pairs.

Each of the following t lines contains two integers p_i and q_i (1 ≤ p_i ≤ 10^{18}; 2 ≤ q_i ≤ 10^{9}) — the i-th pair of integers.

Output

Print t integers: the i-th integer is the largest x_i such that p_i is divisible by x_i, but x_i is not divisible by q_i.

One can show that there is always at least one value of x_i satisfying the divisibility conditions for the given constraints.

Example

Input


3
10 4
12 6
179 822


Output


10
4
179

Note

For the first pair, where p_1 = 10 and q_1 = 4, the answer is x_1 = 10, since it is the greatest divisor of 10 and 10 is not divisible by 4.

For the second pair, where p_2 = 12 and q_2 = 6, note that 

  * 12 is not a valid x_2, since 12 is divisible by q_2 = 6; 
  * 6 is not valid x_2 as well: 6 is also divisible by q_2 = 6. 

The next available divisor of p_2 = 12 is 4, which is the answer, since 4 is not divisible by 6.
import sys;import math;from collections import deque;I=sys.stdin.readline;IN=lambda x:map(int,x.split());L=lambda x:list(IN(x))
Nmax=31623#20000000#4473#;273;73681;
def seive(n):
	l=[]
	prime=[1]*(n+1)
	i=2;m=0
	while(i<=n):
		j=i*i
		l.append(i);m+=1
		while(j<=n):
			prime[j]=i
			j+=i
		i+=1
		while(i<=n and prime[i]!=1):
			i+=1
	return l,prime,m
prime,lis,leng=seive(Nmax)
def li(q):
	l=[];j=0
	while(q>Nmax):
		if(j==leng):
			break
		num=prime[j]
		a,b=divmod(q,num)
		if(b==0):
			l.append(num)
			while(b==0):
				q=a
				a,b=divmod(q,num)
		j+=1
	if(q==1):
		return l
	if(j==leng):
		l.append(q)
		return l
	while(q>1):
		t=lis[q]
		if(t==1):
			l.append(q)
			return l
		l.append(t)
		a,b=divmod(q,t)
		while(b==0):
			q=a
			a,b=divmod(q,t)
	return l
def find(p,q):
	l=li(q)
	j=0;c=0;res=0;z=p
	for i in l:
		if(q%i==0):
			a1=p//i
			while(a1%q==0):
				p=a1
				a1=p//i
			p,res=z,max(res,a1)
	return res
for _ in range(int(I())):
	p,q=IN(I())
	if((p%q)!=0):
		print(p)
		continue
	print(find(p,q))
