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, time
from copy import copy, deepcopy as dcopy
from os import path
from collections import *
from heapq import *
from math import *

#################### Write your code here ######################

def sieve (q) :
	x = 2;
	fact = [];
	while (x * x <= q):
		if (q % x == 0): fact.append(x);
		while (q % x == 0): q //= x;
		x += 1;
	if q > 1 : fact.append(q);
	return fact;

def calc (x, q):
	ans = 0;
	while (q % x == 0):
		ans += 1;
		q //= x;
	return ans

def get(c, p, q):
	det = calc(c, p) - calc(c, q) + 1;
	return int(pow(c, det));

def solve (kkkk):
	p, q = inm();
	gc = gcd(p, q)
	ans = p;
	if (gc == q) :
		pr = sieve(q);
		val = p;
		for x in pr:
			val = min(val, get(x, p, q))
		ans = p // val;
	out(ans)

def main():
    t = 1
    t = inp()
    for i in range(t):	solve(i + 1)

############################# END ##############################
######################## DO NOT TOUCH ##########################

#--------------------- Local Setup Helper ---------------------#

localsys = 0
start_time = time.time()
if (path.exists('input.txt')):
    sys.stdin  = open("input.txt", "r")
    sys.stdout = open("output.txt","w")
    localsys = 1

#-------------------- I/O Functionalities ---------------------#

cin  = sys.stdin.readline
cout = sys.stdout.write
def inp(): return int(cin().strip())
def ins(): return list(cin().strip())
def inm(): return map(int, cin().strip().split())
def ina(): return list(map(int, cin().strip().split()))

def out  (a) : cout(str(a) + "\n")
def outa (a) : cout(" ".join(map(str, a)) + "\n")
def outm (a, b, c = None, d = None) :
	cout(str(a) + " " + str(b))
	if c != None : cout(" " + str(c))
	if d != None : cout(" " + str(d))
	cout("\n")

#---------------------- Code Initiator ------------------------#

main()
if localsys:
	print("\n\nTime Elapsed :",time.time() - start_time,"seconds")

################################################################