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.*;
import java.lang.reflect.Array;
import java.util.*;

public class Main {

    static FastScanner sc;
    static PrintWriter pw;
    static final int INF = 1000000000;

    private static long gcd(long a, long b) {
        long tmp = 0;
        while(b > 0) {
            a %= b;
            tmp = a;
            a = b;
            b = tmp;
        }

        return a;
    }

    private static List<Long> get_primes() {
        List<Long> ans = new ArrayList<>();
        int n = 100000;
        boolean[] t = new boolean[n + 1];
        Arrays.fill(t, true);
        t[0] = false;
        t[1] = false;
        for(int i = 2; i <= n; ++i)
            if(t[i]) {
                ans.add((long) i);
                if ((long) i * i <= n)
                    for (int j = i * i; j <= n; j += i)
                        t[j] = false;
            }
        return ans;
    }

    public static void main(String[] args) throws IOException {
        sc = new FastScanner(System.in);
        pw = new PrintWriter(System.out);
        int t = sc.nextInt();
        List<Long> primes = get_primes();
        for(int tt = 0; tt < t; ++tt) {
            long p = sc.nextLong(), q = sc.nextLong();
            if(p < q || p % q != 0) pw.println(p);
            else {
                long tmp = p, tx = gcd(tmp, q);
                while(tx > 1) {
                    tmp = tmp / tx;
                    tx = gcd(tmp, q);
                }

                long ans = tmp;

                p /= ans;
              //  pw.println(ans);
                Map<Long, Long> m_p = new HashMap<>();
                Map<Long, Long> m_q = new HashMap<>();
                for(Long prime : primes) {
                    while (q > 1 && q % prime == 0) {
                        if (!m_q.containsKey(prime)) m_q.put(prime, 1L);
                        else m_q.put(prime, m_q.get(prime) + 1);
                        q /= prime;
                    }
                }
                if(q > 1) {
                    m_q.put(q, 1L);
                    primes.add(q);
                }

                for(Long prime : primes) {
                    while (p > 1 && p % prime == 0) {
                        if (!m_p.containsKey(prime)) m_p.put(prime, 1L);
                        else m_p.put(prime, m_p.get(prime) + 1);
                        p /= prime;
                    }
                }




                Long res = 1L;
                for(Map.Entry<Long, Long> entry : m_p.entrySet()) {
                    Long pow = entry.getValue();
                    Long ke = 1L;
                    for(int i = 0; i < pow; ++i)
                        ke *= entry.getKey();
                    res *= ke;
                }

                Long pos_ans = 0L;
              //  pw.println(m_p);
               // pw.println(m_q);
                for(Map.Entry<Long, Long> entry : m_p.entrySet()) {
                    Long pow = entry.getValue();
                    long ke = 1;
                    long low = 1;
                    for(int i = 0; i < pow; ++i) {
                        ke *= entry.getKey();
                        if(i == m_q.get(entry.getKey()) - 1)
                            low = ke / entry.getKey();
                    }
                    //pw.println(ke + " " + low + " " + res);
                    pos_ans = Math.max(res / ke * low, pos_ans);
                }

                pw.println( ans * pos_ans);
            }
        }
        pw.close();
    }
}

class FastScanner {
    static StringTokenizer st = new StringTokenizer("");
    static BufferedReader br;

    public FastScanner(InputStream inputStream) {
        br = new BufferedReader(new InputStreamReader(inputStream));
    }

    public String next() throws IOException {
        while (!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());
    }
}