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 collections
import math
import collections
import sys

from functools import reduce
import decimal

sys.setrecursionlimit(10 ** 9)
decimal.getcontext().rounding = decimal.ROUND_HALF_UP

graphDict = collections.defaultdict
queue = collections.deque


class Graphs:
    def __init__(self):
        self.graph = graphDict(list)

    def add_edge(self, u, v):
        self.graph[u].append(v)

    def dfs_utility(self, nodes, visited_nodes):
        visited_nodes.add(nodes)
        for neighbour in self.graph[nodes]:
            if neighbour not in visited_nodes:
                self.dfs_utility(neighbour, visited_nodes)
            else:
                return neighbour

    def dfs(self, node):
        Visited = set()
        self.dfs_utility(node, Visited)

    def bfs(self, node):
        visited = set()
        if node not in visited:
            queue.append(node)
            visited.add(node)
        while queue:
            parent = queue.popleft()
            print(parent)
            for item in self.graph[parent]:
                if item not in visited:
                    queue.append(item)
                    visited.add(item)


def rounding(n):
    return int(decimal.Decimal(f'{n}').to_integral_value())


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


def inp():
    return sys.stdin.readline().strip()


def map_inp(v_type):
    return map(v_type, inp().split())


def list_inp(v_type):
    return list(map_inp(v_type))


######################################## Solution ####################################


for _ in range(int(inp())):
    p, q = map_inp(int)
    temp_q = q
    if p < q:
        print(p)
    elif p % q != 0:
        print(p)
    else:
        fac = []
        for i in range(2, int(q ** 0.5) + 1):
            if temp_q % i == 0:
                fac.append(i)
                while temp_q % i == 0:
                    temp_q //= i
        if temp_q > 1:
            fac.append(temp_q)
        ans = 1
        for item in fac:
            temp = p
            while temp % q == 0:
                temp //= item
            ans = max(ans, temp)
        print(ans)
