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.io.*;
import java.math.BigInteger;
public class MyClass {
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()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 
    public static ArrayList<Long> primeFactorize(long n) {
        ArrayList<Long> primeFactors = new ArrayList<Long>();
        
        long primeFactor = 0L;

        for (long i = 2L; i <= n / i; ) { // smallest prime factor to the square root of n (largest possible factor of n)
            if (n % i == 0) { // the prime number i is a factor of n (i will never go into n if it's composite since the prime factor of that compositite number would have already been tested)
                primeFactor = i; // therefore, this is a prime factor of n
                primeFactors.add(primeFactor);
                n /= i; // divide out that prime factor from n to get the rest of the prime factors
                // don't increment i: test if this same prime factor goes into n multiple times (e.g. 18 = 2*3*3)
            } else {
                i++; // i is not a prime factor of n, so increment
            }
        }
        
        if (primeFactor < n) { // n had no more prime factors, so n is a prime factor
            primeFactors.add(n);
        } else { // n was divided down to 1, meaning that the last prime factor divided itself out. therefore, it is the last prime factor
            primeFactors.add(primeFactor);
        }
        
        return primeFactors;
    }
    
    /**
     * Reduces the parameter n into a product of only prime numbers
     * and returns a list of those prime number factors as BigIntegers.
     * 
     * @param  n  the number to prime factorize
     * @return an ArrayList (of BigIntegers) of only prime factors of the parameter n
     */
    public static ArrayList<BigInteger> primeBigFactorize(BigInteger n) {
        ArrayList<BigInteger> primeFactors = new ArrayList<BigInteger>();
        BigInteger primeFactor = BigInteger.ZERO;
    
        for (BigInteger i = new BigInteger("2"); i.compareTo(n.divide(i)) <= 0; ) {
            if (n.mod(i).longValue() == 0) {
                primeFactor = i;
                primeFactors.add(primeFactor);
                n = n.divide(i);
            } else {
                i = i.add(BigInteger.ONE);
            }
        }
        
        if (primeFactor.compareTo(n) < 0) {
            primeFactors.add(n);
        } else {
            primeFactors.add(primeFactor);
        }
        
        return primeFactors;
    }
    
    public static void main(String args[]) 
{
	FastReader s=new FastReader();int t=0;long p=0,q=0,qq=0;
     //Scanner in=new Scanner(System.in);
     //if(in.hasNext())
     t=s.nextInt();
     for(int j=0;j<t;j++)
     {
      //   if(in.hasNext())
         p=s.nextLong();
         q=s.nextLong();
         qq=q;
         if(p%q!=0)
         System.out.println(p);
         else
         {
             ArrayList<BigInteger> al2=new ArrayList<>();
            al2=primeBigFactorize(new BigInteger(Long.toString(q)));
            ArrayList<Long> al=new ArrayList<>();
            for(int i=0;i<al2.size();i++)
            {
                al.add(al2.get(i).longValue());
            }
            long ans = 1;
		for(int i=0;i<al.size(); i++){
			long n = p;
			while(n % qq == 0) n /= al.get(i);
			ans = Math.max(ans, n);
		}
		System.out.println(ans);
         }
     }
    }
}