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.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class Main {

    public static void main(String[] args){
        try {
            PrintWriter out=new PrintWriter(System.out,true);
            BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
            int t = Integer.parseInt(br.readLine());
            for(int i=0;i<t;i++) {

                String[] ss = br.readLine().split(" ");
                long p = Long.parseLong(ss[0]);
                long q = Long.parseLong(ss[1]);
                if (p % q != 0) {
                    out.println(p);
                    continue;
                }
                List<pair> list = new ArrayList<>();

                for(long j=2;j*j<=q;j++){
                    if(q%j==0){
                        int cnt=0;
                        while(q%j==0){
                            q=q/j;
                            cnt++;
                        }
                        list.add(new pair(j,cnt));
                    }
                }
                if(q>1){
                    list.add(new pair(q,1));
                }
                long ans=1;
                for(int j=0;j<list.size();j++){
                    pair pp = list.get(j);
                    long f = pp.a , s=pp.b;
                    long x = p;
                    while(x%f==0){
                        x=x/f;
                    }
                    for(int k=1;k<s;k++){
                        x=x*f;
                    }
                    ans=Math.max(ans,x);

                }
                out.println(ans);

            }



            out.close();
        } catch (Exception e) {
            System.out.println("kkkk "+e.toString());
        }
    }
    static void sieveOfEratosthenes(int n) {
        boolean[] prime = new boolean[n+1];
        for(int i=0;i<n;i++)
            prime[i] = true;
        for(int p = 2; p*p <=n; p++)
        {
            if(prime[p])
            {
                for(int i = p*p; i <= n; i += p)
                    prime[i] = false;
            }
        }
    }
    static void swap(int[] arr,int i,int j){
        int temp = arr[i-1];
        arr[i-1] = arr[j-1];
        arr[j-1] = temp;
    }


    static int diff(String s1,String s2){
        int c=0;
        for(int i=0;i<s1.length();i++){
            if(s1.charAt(i)!=s2.charAt(i)){
                c++;
            }
        }
        return c;
    }
    static boolean isPal(String s){
        StringBuilder str=new StringBuilder(s);
        str=str.reverse();
        String ss=String.valueOf(str);
        if (ss.equals(s)) {
            return true;
        }
        return false;
    }
    static int mod(int a,int b){
        if (a>b){
            return a-b;
        }
        return b-a;
    }
    static void shuffle(int[] a) {
        Random get = new Random();
        for (int i = 0; i < a.length; i++) {
            int r = get.nextInt(a.length);
            int temp = a[i];
            a[i] = a[r];
            a[r] = temp;
        }
    }
    static int lcm(int a,int b){
        long c=a*((long)b);
        return (int)(c/hcf(a,b));
    }
    static int hcf(int a,int b){
        if(a==0){
            return b;
        }
        if(b==0){
            return a;
        }
        if(a>b)
            return hcf(a%b,b);

        return hcf(a,b%a);
    }

    static int modInverse(int x,int m){
        return power(x,m-2,m);
    }
    static int power(int x, int y, int m)
    {
        if (y == 0)
            return 1;

        long p = power(x, y / 2, m) % m;
        p = (p * p) % m;

        return (int)((y%2==0)? p : (x*p)%m);
    }
    static class pair{
        long a,b;
        public pair(long a,long b){
            this.a=a;
            this.b=b;
        }
    }
}