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 com.sun.org.apache.xpath.internal.SourceTree;
import com.sun.org.apache.xpath.internal.functions.FuncFalse;
import javafx.util.Pair;

import java.io.*;
import java.util.*;

import static java.lang.Math.*;

public class Contest {
    public static class pair implements Comparable<pair> {
        long l;
        long r;


        public pair(long lef, long ri) {
            l = lef;
            r = ri;
        }

        @Override
        public int compareTo(pair p) {
            if (l == p.l)
                return Long.compare(r, p.r);
            return Long.compare(l, p.l);
        }
    }

    static int n, m;
    static ArrayList<Integer>[] adj;
    static int dist[];
    static int[] h;
    static int[] p;
    static int parent[];
    static long inf = (long) 1e18;
    static int INF = (int) 1e9;


    public static boolean isSimilar(char[] Arr, int s, int k) {
        for (int i = s; i < k - 1; i++) {
            if (Arr[i + 1] != Arr[i])
                return false;
        }
        return true;
    }

    public static int ciel(int d, int mod) {
        if (d % mod == 0)
            return d / mod;
        return (d / mod) + 1;
    }


    public static long gcd(long u, long v) {
        if (v == 0)
            return u;
        return gcd(v, u % v);
    }

    static int k, Arr[], lefAcc[], riAcc[];
    static PrintWriter pw;

    static long memo[][];
    static char[][] Matrix;
    static int[][] dp;
//    static int[] dx = new int[]{-1, 1, 0, 0};
//
//    static int[] dy = new int[]{0, 0, -1, 1};


    static boolean valid(int i, int j) {

        return i != -1 && j != -1 && i != n && j != m;

    }


    static boolean[][] vis, vis1, explored;
    static int x, y;

//    static void dfs2(int i, int j) {
//        vis[i][j] = true;
//        //mark as visited
//        for (int k = 0; k < 4; ++k) {
//            int x = i + dx[k], y = j + dy[k];
//            if (valid(x, y) && Matrix[x][y] != '#' && !vis[x][y])
//                dfs2(x, y);
//        }
//    }

    static boolean hasMore = false;

//    static void dfs1(int i, int j) {
//        vis1[i][j] = true;
//        //mark as visited
//        int ans = 0;
//        for (int k = 0; k < 4; ++k) {
//
//            int x = i + dx[k], y = j + dy[k];
//            if (valid(x, y) && Matrix[x][y] != '#') {
//                if (!vis1[x][y])
//                    dfs1(x, y);
//                if (vis[x][y]) ans++;
//            }
//        }
//        if (ans > 2) hasMore = true;
//    }

//    public static int getnum(int[][] matrix, int i, int j) {
//        int c = 0;
//
//        for (int k = 0; k < 4; ++k) {
//
//            int x = i + dx[k], y = j + dy[k];
//
//            if (valid(x, y))
//                c++;
//
//        }
//        return c;
//    }

    static char fir, sec;

    static long nCK3(long N, long K) {        // O(K)
        if (K > N)
            return 0;
        long res = 1;
        for (int i = 1; i <= K; ++i) {
            res = (N - K + i) * res / i;
            res %= mod;
        }
        return res;
    }

    static long mod = (int) (1e9 + 7);
    static double ax, bx, cx, dx, ay, by, cy, dy, angle1, angle2, d1, d2, cos1, sin1, cos2, sin2;

    public static double chDist(double mid) {
        double x1, y1, x2, y2;
        if (mid <= d1) {
            x1 = mid * cos1 + ax;
            y1 = mid * sin1 + ay;
        } else {
            x1 = bx;
            y1 = by;
        }
        if (mid <= d2) {
            x2 = mid * cos2 + cx;
            y2 = mid * sin2 + cy;
        } else {
            x2 = dx;
            y2 = dy;
        }
        return sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
    }

    static double epc = 1e-8;
    static long poww(long a, int n)
    {
        long res = 1;
        while(n != 0)
        {
            if((n & 1) == 1)
                res *= a;
            a *= a;
            n >>= 1;
        }
        return res;
    }
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        pw = new PrintWriter(System.out);
        int t = sc.nextInt();
        while (t-- > 0) {
//            n=sc.nextInt();
            long p = sc.nextLong();
            long q = sc.nextLong();
            long ans = 1;
            ArrayList<Long> arr = new ArrayList<>();
            if (p % q != 0) {
                pw.println(p);
            } else {
                for (int i = 2; i * i <= q; i++) {
                    if (q % i == 0) {
                        arr.add((long) i);
                        arr.add(q / i);
                    }
                }
                arr.add(q);
                for (long x : arr) {
                    Long pp = p;
                    long qq = q;
                    int cntq = 0;
                    while (qq % x == 0) {
                        cntq++;
                        qq /= x;
                    }
                    int cntp = 0;
                    while (pp % x == 0) {
                        cntp++;
                        pp /= x;
                    }
                    int y=cntp-cntq+1;
                    ans=  max(ans,p/((poww(x,y))));
                }
                pw.println(ans);
            }
        }

        pw.close();


    }

    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public String nextLine() throws IOException {
            return br.readLine();
        }

        public double nextDouble() throws IOException {
            String x = next();
            StringBuilder sb = new StringBuilder("0");
            double res = 0, f = 1;
            boolean dec = false, neg = false;
            int start = 0;
            if (x.charAt(0) == '-') {
                neg = true;
                start++;
            }
            for (int i = start; i < x.length(); i++)
                if (x.charAt(i) == '.') {
                    res = Long.parseLong(sb.toString());
                    sb = new StringBuilder("0");
                    dec = true;
                } else {
                    sb.append(x.charAt(i));
                    if (dec)
                        f *= 10;
                }
            res += Long.parseLong(sb.toString()) / f;
            return res * (neg ? -1 : 1);
        }

        public boolean ready() throws IOException, IOException {
            return br.ready();
        }

    }
}

