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.
/*
                       _oo0oo_
                      o8888888o
                      88" . "88
                      (| -_- |)
                      0\  =  /0
                    ___/`---'\___
                  .' \\|     |// '.
                 / \\|||  :  |||// \
                / _||||| -:- |||||- \
               |   | \\\  -  /// |   |
               | \_|  ''\---/''  |_/ |
               \  .-\__  '-'  ___/-. /
             ___'. .'  /--.--\  `. .'___
          ."" '<  `.___\_<|>_/___.' >' "".
         | | :  `- \`.;`\ _ /`;.`/ - ` : | |
         \  \ `_.   \_ __\ /__ _/   .-` /  /
     =====`-.____`.___ \_____/___.-`___.-'=====
                       `=---='
 
*/
import java.util.function.Consumer;
import java.util.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.text.DecimalFormat;
import java.io.*;
import java.lang.Math.*;
 public class KickStart2020{
	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());}
        float nextFloat() {return Float.parseFloat(next());}
        String nextLine() {
            String str = "";
            try {str = br.readLine();}
            catch (IOException e) { e.printStackTrace();}
            return str; }}
	static boolean isBracketSequence(String s, int a, int b) {
		Stack<Character> ss = new Stack<>();
		boolean hachu = true;
		for(int i = a; i <= b; i++) {
			if(s.charAt(i) == ')' && ss.isEmpty()) {hachu = false; break;}
			if(s.charAt(i) == '(') ss.add('(');
			else ss.pop();
		}
		return ss.empty() && hachu;
	}
	static String reverseOfString(String a) {
		StringBuilder ssd = new StringBuilder();
		for(int i = a.length() - 1; i >= 0; i--) {
			ssd.append(a.charAt(i));
		}
		return ssd.toString();
	}
	static char[] reverseOfChar(char a[]) {
		char b[] = new char[a.length];
		int j = 0;
		for(int i = a.length - 1; i >= 0; i--) {
			b[i] = a[j];
			j++;
		}
		return b;
	}
	static boolean isPalindrome(char a[]) {
		boolean hachu = true;
		for(int i = 0; i <= a.length / 2; i++) {
			if(a[i] != a[a.length - 1 - i]) {
				hachu = false;
				break;
			}
		}
		return hachu;
	} 
	static long gcd(long a, long b)
	{
	    if (b == 0)
	        return a;
	    return gcd(b, a % b);
	     
	}
	static long powermod(long x, long y, long mod){
	    long ans = 1;
	    x = x % mod; 
	    if (x == 0)
	      return 0; 
	    int i = 1;
	    while (y > 0){
	      if ((y & 1) != 0)
	        ans = (ans * x) % mod;
	      y = y >> 1; 
	      x = (x * x) % mod;
	    }
	    return ans;
	  }
	static long power(long x, long y){
	    long ans = 1;
	    if (x == 0)
	      return 0; 
	    int i = 1;
	    while (y > 0){
	      if ((y & 1) != 0)
	        ans = (ans * x);
	      y = y >> 1; 
	      x = (x * x);
	    }
	    return ans;
	  }
	static boolean check(String a) {
		boolean hachu = true;
		for(int i = 0; i < a.length(); i++) {
			if(a.charAt(0) != a.charAt(i)) {hachu = false; break;}
		}
		return hachu;
	}
	 public static class Pair implements Comparable<Pair> {
	        public  int index;
	        public  int value;
	 
	        public Pair(int index, int value) {
	            this.index = index;
	            this.value = value;
	        }
	        @Override
	        public int compareTo(Pair other) {
	            //multiplied to -1 as the author need descending sort order
	            return   -1 * Integer.valueOf(this.value).compareTo(other.value);
	        }
	 }
	 static boolean equalString(int i, int j, int arr[], String b) {
		 int brr[] = new int[26];
		 for(int k = i; k <= j; k++) brr[b.charAt(k) - 'a']++;
		 for(int k = 0; k < 26; k++) {
			 if(arr[k] != brr[k]) return false;
		 }
		 return true;
	 }
	 static boolean cequalArray(String a, String b) {
		  int count[] = new int[26];
		  int count1[] = new int[26];
		  for(int i = 0; i < a.length(); i++) count[a.charAt(i) - 'a']++;
		  for(int i = 0; i < a.length(); i++) count1[b.charAt(i) - 'a']++;
		  for(int i = 0; i < 26; i++) if(count[i] != count1[i]) return false;
		  return true;
	 }
	 static boolean isPrime(long d) {
		 if(d == 1) return true;
		 for(int i = 2; i <= (long)Math.sqrt(d); i++) {
			 if(d % i == 0) return false;
		 }
		 return true;
	 }
		public static void main(String[] args) throws Exception{
			FastReader sc = new FastReader();
			PrintWriter out = new PrintWriter(System.out);
             int t = sc.nextInt();
             while(t-- > 0) {
               long p = sc.nextLong();
               int q = sc.nextInt();
               HashSet<Long> ss = new HashSet<>();
               int temp = q;
               outerloop:
               while(temp > 1) {
            	   for(int i = 2; i * i <= temp; i++) {
            		   if(temp % i == 0) {
            			   temp /= i;
            			   ss.add(i * 1l);
            			   continue outerloop;
            		   }
            	   }
            	   ss.add(temp * 1l);
            	   break;
               }
//               out.println();
               long max = 1;
               for(long e: ss) {
            	   long temp1 = p;
            	   while(temp1 % q == 0) {
            		   temp1 /= e;
//            		   out.print(temp1 + " ");
            	   }
//            	   out.println();
            	   max = Math.max(temp1, max);
               }
               out.println(max);
             }
                 out.close();
			}
		}