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
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__
import math
from functools import reduce
from math import sqrt

def factors(n):
        step = 2 if n%2 else 1
        return set(reduce(list.__add__,
                    ([i, n//i] for i in range(1, int(sqrt(n))+1, step) if n % i == 0)))

from collections import defaultdict
# A function to print all prime factors of  
# a given number n 
def primeFactors(n): 
    ans = defaultdict(lambda:0)
    # Print the number of two's that divide n 
    while n % 2 == 0: 
        ans[2]+=1 
        n = n // 2
          
    # n must be odd at this point 
    # so a skip of 2 ( i = i + 2) can be used
    while n!=1:
        found=False
        for i in range(3,int(math.sqrt(n))+1,2):   
            if n % i== 0:
                found=True
                ans[i]+=1
                n = n // i
                break
        if not found:
            ans[n]+=1
            n = 1
    return list(ans.items())


def gift():
    for _ in range(t):
        xi,pi = list(map(int,input().split()))


        if pi>xi:
            yield xi
        else:
            if xi%pi:
                yield xi
            else:
                #print(xi,pi)
                right = pi
                array = sorted(factors(right),reverse=True)
                ans = 1
                for ele in array:
                    if (xi//ele)%right:
                        ans=max(ans,xi//ele)
                pFactors = primeFactors(pi)

                for i in range(len(pFactors)):
                    counter=1
                    while True:
                        now = pFactors[i][0]**(pFactors[i][1]+counter)
                        if xi%(now)==0:
                            if (xi//now%pi):
                                ans = max(ans,xi//now)
                        else:
                            break
                        counter+=1
                yield ans
                    


        
if __name__ == '__main__':
    t= int(input())
    ans = gift()
    print(*ans,sep='\n')
            

# 10000 100
# 100 100
# 2 2 5 5
# 2 2 5 5
#"{} {} {}".format(maxele,minele,minele)
