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.BufferedOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.*;
import java.util.InputMismatchException;
import java.util.stream.IntStream; 
public class A
{
    public static void solve()
    {
        int t=sc.nextInt();
        while (t-->0)
        {
           long p=sc.nextLong();
           long q=sc.nextLong();
           if (p%q!=0) {
        	   out.println(p);
        	   continue;
           }
           long ans=1;
           for (long i=1; i*i <=q;i++) {
        	   if (q%i==0) {
        		   if (i!=1) {
        			   long pNew=p;
        			   while (pNew%q==0)
        				   pNew/=i;
        			   ans = Math.max(ans,pNew);
        		   }
        		   long j=q/i;
    			   long pNew=p;
    			   while (pNew%q==0)
    				   pNew/=j;
    			   ans=Math.max(ans, pNew);
        	   }
           }
           out.println(ans);
        }
    }
    public static void main(String[] args) 
    {
        new Thread(null, null, "Thread", 1 << 27) 
        {
            public void run() 
            {
                try 
                {
                    out = new PrintWriter(new BufferedOutputStream(System.out));
                    sc = new FastReader(System.in);
                    solve();
                    out.close();
                } 
                catch (Exception e) 
                {
                    e.printStackTrace();
                    System.exit(1);
                }
            }
        }
                .start();
    }
    static int N = 2*100000+1;
    static int[] freq(int[] a,int n) {
    	int[] frequency=new int[N];
    	for (int i=0;i<n;i++) frequency[a[i]]++;
    	return frequency;
    }
    static int count(int[] a,int t) {
    	int n=a.length;
    	int[] cnt=freq(a,n);
    	int x=cnt[t]+1;
    	if (x-1==n) return 0;
    	for (int i=0;i<n;i++) {
    		if (i==0) {
    			if ( a[i]==t && a[i]==a[n-1] ) {
    				x-=2;
    			}
    			else if (a[i]==t && a[i]!=a[n-1]) x--;
    		}
    		else if(i<n-1) {
    			if (a[i]==t && a[i]==a[i+1]) x--;
    		}
    		else {
    			if (a[i]==t && a[0]!=a[i]) x--;
    		}
    	}
    	return x;
    }
    public static int Index(int arr[], int t) 
    { 
        int len = arr.length; 
        return IntStream.range(0, len) 
            .filter(i -> t == arr[i]) 
            .findFirst() // first occurrence 
            .orElse(-1); // No element found 
    } 
    static final Random random=new Random();
    static int gcd(int a,int b)
    {
        if (b==a)
            return a;
        return gcd(b,a%b);
    }
    static void UjjwalSort(int[] a) 
    {
        int n=a.length;//shuffle, then sort 
        for (int i=0; i<n; i++) 
        {
            int ujjwal=random.nextInt(n), temp=a[ujjwal];
            a[ujjwal]=a[i]; a[i]=temp;
        }
        Arrays.sort(a);
    }
    public static PrintWriter out;
    public static FastReader sc;
    public static class FastReader 
    {
        private InputStream stream;
        private byte[] buf = new byte[4096];
        private int curChar, snumChars;
        public FastReader(InputStream stream) 
        {
            this.stream = stream;
        }
        public int read() 
        {
            if (snumChars == -1) 
            {
                throw new InputMismatchException();
            }
            if (curChar >= snumChars) 
            {
                curChar = 0;
                try 
                {
                    snumChars = stream.read(buf);
                } 
                catch (IOException E) 
                {
                    throw new InputMismatchException();
                }
            }
            if (snumChars <= 0) 
            {
                return -1;
            }
            return buf[curChar++];
        }
        public int nextInt() 
        {
            int c = read();
            while (isSpaceChar(c)) 
            {
                c = read();
            }
            int sgn = 1;
            if (c == '-') 
            {
                sgn = -1;
                c = read();
            }
            int number = 0;
            do 
            {
                number *= 10;
                number += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return number * sgn;
        }
        public long nextLong() {
            int c = read();
            while (isSpaceChar(c)) 
            {
                c = read();
            }
            long sgn = 1;
            if (c == '-') 
            {
                sgn = -1;
                c = read();
            }
            long number = 0;
            do 
            {
                number *= 10L;
                number += (long) (c - '0');
                c = read();
            } while (!isSpaceChar(c));
            return number * sgn;
        }
        public int[] nextIntArray(int n) 
        {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) 
            {
                arr[i] = this.nextInt();
            }
            return arr;
        }
        public long[] nextLongArray(int n) 
        {
            long[] arr = new long[n];
            for (int i = 0; i < n; i++) 
            {
                arr[i] = this.nextLong();
            }
            return arr;
        }
        public String next()
        {
            int c = read();
            while (isSpaceChar(c)) 
            {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do 
            {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }
        public String nextLine() 
        {
            int c = read();
            while (isSpaceChar(c)) 
            {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do
            {
                res.appendCodePoint(c);
                c = read();	
            } while (!isEndofLine(c));
            return res.toString();
        }
        public boolean isSpaceChar(int c)
        {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
        public boolean isEndofLine(int c) 
        {
            return c == '\n' || c == '\r' || c == -1;
        }
    }
}
