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.
//WHEN IN DOUBT , USE BRUTE FORCE !!!!!!!!!
import java.lang.String;
import java.io.*;
import java.util.*;
import java.util.StringTokenizer;
//class Main    //AtCoder
//class Solution // Codechef
public class Solution2 //Codeforces
{
    public static void main(String args[])
    {
        try {
            FastReader sc = new FastReader();
            int TT = sc.nextInt();
            for(int hehe=1 ; hehe  <= TT ; hehe++){
                long p=sc.nextLong();
                long q=sc.nextLong();
                if(p < q)
                    sopln(p);
                else if(p%q != 0){
                    sopln(p);
                }
                else{
                    Map<Long,Long> pFactor=primeFactors(q);
                    long temp=p;
                    long max=1;
                    //sopln(pFactor);
                    for(long prime : pFactor.keySet())
                    {
                        long pGet=pFactor.get(prime);
                        long divisor=(long)Math.pow(prime , pGet),cnt=0;temp=p;
                        while(temp%prime == 0){
                            temp/=prime;
                            cnt++;
                        }
                        if(cnt > 0){
                            if(cnt >= pGet){
                                long divPow=cnt-pGet+1;
                                long div=p/(long)(Math.pow(prime,divPow));
                                max=Math.max(max,div);
                            }
                        }
                    }
                    sopln(max);
                }
            }
            out.flush();
        }catch (Exception e) {
            sopln(e.toString());
        }
    }

    private static Map<Long,Long> primeFactors(long n) {
        Map<Long,Long> ll=new TreeMap<>();
        long nn=n;
        while (nn%2l == 0l)
        {
            ll.put(2l , ll.getOrDefault(2l,0l)+1);
            nn /= 2l;
        }
        for (long i = 3; i <= (long)Math.sqrt(n); i+= 2l)
        {
            while (nn%i == 0l)
            {
                ll.put((long)i , ll.getOrDefault(i,0l)+1l);
                nn /= i;
            }
        }
        if (nn > 2l)
            ll.put((long)nn , ll.getOrDefault(nn,0l)+1);
        return ll;
    }

    public final static int d = 256;
    static int MOD = 1000000007;
    static final double PI = Math.PI;
    private static BufferedReader in = new BufferedReader (new InputStreamReader (System.in));
    private static PrintWriter out = new PrintWriter (new OutputStreamWriter (System.out));
    static class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader()
        {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException  e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

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

        char nextChar()
        {
            try {
                return (char) (br.read());
            }catch (IOException e){
                return '~';
            }
        }

        double nextDouble()
        {
            return Double.parseDouble(next());
        }

        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }
    static void sop(Object o){System.out.print(o);}
    static double ceil(double d){
        return Math.ceil(d);
    }
    static double floor(double d){
        return Math.floor(d);
    }
    static double round(double d){
        return Math.round(d);
    }
    static void sopln(Object o){System.out.println(o);}
    static void printArray(char arr[]){
        for(char L:arr)
            sop(L+" ");
        sopln("");
    }

}