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.
from __future__ import print_function # for PyPy2
from collections import Counter, OrderedDict
from itertools import permutations as perm
from collections import deque
from sys import stdin
from bisect import *
from heapq import *
import math
 
g   = lambda : stdin.readline().strip()
gl  = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
mod = int(1e9)+7
inf = float("inf")

t, = gil()

def primeFactors(n): 
	ans = {}
	# Print the number of two's that divide n 
	while n % 2 == 0: 
		# print 2,
		ans[2] = ans.get(2, 0) + 1 
		n = n // 2
		  
	# n must be odd at this point 
	# so a skip of 2 ( i = i + 2) can be used 
	for i in range(3,int(math.sqrt(n))+1,2): 
		  
		while n % i== 0: 
			# print i,
			ans[i] = ans.get(i, 0) + 1 
			n = n // i 
			  
	# Condition if n is a prime 
	# number greater than 2 
	if n > 2: 
		ans[n] = ans.get(n, 0) + 1

	return ans

# print(primeFactors(12))
# print(primeFactors(6))
def getPower(x, p):
	l, r = 1, int(math.ceil(math.log(p, x)))
	ans = 1
	while l <= r:
		mid = (l+r)//2
		# print( p%(x**mid), p, x, mid)
		if p%(x**mid) != 0:
			r = mid - 1
		else:
			l = mid + 1
			ans = mid
	return ans

# print(">>", 3, 6, getPower(3, 6))

for _ in range(t):
	p, q = gil()
	ans = inf
	if p%q:
		print(p)
	else:
		fac = primeFactors(q)
		for f in fac:
			v =getPower(f, p)
			ans = min((f**(v-fac[f]+1)), ans)

		print(p//ans)