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 java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Map;
import java.util.Scanner;
import java.util.HashMap;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main
{
    public static void main(String[] args)
    {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskC
    {
        public void solve(int testNumber, Scanner in, PrintWriter out)
        {
            int T = in.nextInt();
            while (T-- > 0)
            {
                solveOne(in, out);
            }
        }

        private void solveOne(Scanner in, PrintWriter out)
        {
            long p = in.nextLong();
            long q = in.nextLong();

            if (p % q != 0)
            {
                out.println(p);
                return;
            }
            Map<Integer, Integer> fact = CPUtils.factorize((int) q);
            long max = 1;

            for (int prime : fact.keySet())
            {
                int cnt = fact.get(prime);
                long pp = p;

                while (pp % prime == 0)
                    pp /= prime;

                if (pp % q != 0)
                {
                    max = Math.max(max, pp);
                }
                for (int i = 0; i < cnt; i++)
                {
                    pp *= prime;
                    if (pp % q != 0)
                    {
                        max = Math.max(max, pp);
                    }
                }

            }
            out.println(max);
        }

    }

    static class CPUtils
    {
        public static Map<Integer, Integer> factorize(int N)
        {
            Map<Integer, Integer> factors = new HashMap<>();
            while (N % 2 == 0)
            {
                factors.put(2, factors.getOrDefault(2, 0) + 1);
                N /= 2;
            }
            for (int i = 3; i <= Math.sqrt(N); i += 2)
            {
                while (N % i == 0)
                {
                    factors.put(i, factors.getOrDefault(i, 0) + 1);
                    N /= i;
                }
            }
            if (N > 2)
                factors.put(N, factors.getOrDefault(N, 0) + 1);
            return factors;
        }

    }
}

