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

public final class division{
    public static void main(String[] args) throws java.lang.Exception{
        Reader r = new Reader();
        r.init(System.in);
        int t = r.nextInt();
        while(t-->0){
            long p = r.nextLong();
            long q = r.nextLong();
            if(p%q!=0) {
                System.out.println(p);
                continue;
            } 
            HashMap<Long,Long> qprime = new HashMap<>();

            long n = q;
            long count = 0;
            while (n % 2 == 0) { 
                count++;
                n /= 2; 
            } 
            qprime.put(2L,count);
         
            for (long i = 3; i <= Math.sqrt(n); i += 2) { 
                count =0 ;
                while (n % i == 0) { 
                    count++; 
                    n /= i; 
                }
                qprime.put(i,count); 
            } 
            if (n > 2) 
                qprime.put(n,1L);
            // System.out.println(qprime);
            long ans = Integer.MIN_VALUE;
            long temp =0;
            for (Map.Entry<Long,Long> entry : qprime.entrySet()){
                temp =p;
                if(entry.getValue()>0L){
                    while(temp%entry.getKey()==0) temp /= entry.getKey();
                    for(long i=1;temp<=p && i<entry.getValue();i++) temp*= entry.getKey();
                    ans = Math.max(ans,temp);
                }
                
            }

            System.out.println(ans);
        }
    
    }



    static long gcd(long a, long b){
        if(a==0) return b;
        return gcd(b%a, a);
    }

    /** Class for buffered reading int and double values */
    static class Reader {
        static BufferedReader reader;
        static StringTokenizer tokenizer;
    
        /** call this method to initialize reader for InputStream */
        static void init(InputStream input) {
            reader = new BufferedReader(
                        new InputStreamReader(input) );
            tokenizer = new StringTokenizer("");
        }
    
        /** get next word */
        static String next() throws IOException {
            while ( ! tokenizer.hasMoreTokens() ) {
                //TODO add check for eof if necessary
                tokenizer = new StringTokenizer(
                    reader.readLine() );
            }
            return tokenizer.nextToken();
        }
    
        static int nextInt() throws IOException {
            return Integer.parseInt( next() );
        }
        static long nextLong() throws IOException {
            return Long.parseLong( next() );
        }
        static double nextDouble() throws IOException {
            return Double.parseDouble( next() );
        }
    }
}