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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter; // System.out is a PrintWriter
import java.util.HashSet;
// import java.util.Arrays;
import java.util.ArrayList;
// import java.util.Collections;    //  for ArrayList sorting mainly
// import java.util.HashMap;
// import java.util.Random;
import java.util.StringTokenizer;

public class C {
    public static void main(String[] args) throws IOException {
        FastScanner scn = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);
        int tc = scn.nextInt();
        while (tc-- > 0) {
            long P = scn.nextLong(), res = 1L;
            int Q = scn.nextInt();
            if (P % Q != 0) {
                out.println(P);
            } else {
                ArrayList<Integer> factors = factor(Q);
                for (int f : factors) {
                    long p = P;
                    while (p % f == 0) {
                        p /= f;
                        if (p % Q != 0) {
                            res = Math.max(res, p);
                            break;
                        }
                    }
                }
                out.println(res);
            }
        }
        out.close();
    }

    private static ArrayList<Integer> factor(int Q) {
        ArrayList<Integer> res = new ArrayList<>();
        res.add(Q);
        for (int i = 2; i * i <= Q; i++) {
            if (Q % i == 0) {
                res.add(i);
                if (Q / i == i) continue;
                res.add(Q / i);
            }
        }
        return res;
    }

    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        FastScanner() {
            this.br = new BufferedReader(new InputStreamReader(System.in));
            this.st = new StringTokenizer("");
        }

        String next() {
            while (!st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException err) {
                    err.printStackTrace();
                }
            }
            return st.nextToken();
        }

        String nextLine() {
            if (st.hasMoreTokens()) {
                return st.nextToken("").trim();
            }
            try {
                return br.readLine().trim();
            } catch (IOException err) {
                err.printStackTrace();
            }
            return "";
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
        
        long nextLong() {
            return Long.parseLong(next());
        }

    }
}
