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.*;
import java.text.DecimalFormat;
import java.util.*;
    public class educational97A {
    	
 
	public static void main(String[] args) throws Exception {
		PrintWriter pw = new PrintWriter(System.out);
		File file;
		Scanner sc = new Scanner(System.in);
	sieve(1000000);
		int t=Integer.parseInt(sc.next());
		while(t-->0) {
 p=sc.nextLong();
 q=sc.nextLong();
if(p%q!=0) {
	System.out.println(p);
}
else  {
	System.out.println(solve());
}
}
 pw.flush();
 pw.close();

}
	static long p;
	static long q;
	static long solve(){
	
	long temp=p;
	long ans=Integer.MIN_VALUE;
		primefactors(q);	
		for(int i=0;i<factors.size();i++) {
			Pair x=factors.get(i);
			temp=p;
			while(temp>0) {
				temp=temp/x.a;
			
				if((temp)%q!=0) {
					ans=Math.max(ans, temp);
					break;
				}
			}
	         
	        
	    }
			return ans;}
static 	long mod=1000000007;
	static void fact() 
    { fact=new long[1001];
      fact[0]=1;
      fact[1]=1;
      for(int i=2;i<1001;i
    		  ++) {
    	  fact[i]=((i%mod)*(fact[i-1]%mod))%mod;
      }
    } 
  
    static long npr (int n, int r) 
    { 
        return fact[n] / fact[n - r]; 
    } 
  static long fact[];
	static int[]indices;
	static int cnmax;
	static int cnmin;
	public static void binaryasearch(int pos) {
	int left=0;
	int right=indices.length-1;
	
	while(left<right) {
		int mid=(left+right)/2;
		if(indices[mid]<=pos) {
			left=mid+1;
		    cnmax++;		    
		}
		else {
			right=mid;
			cnmin++;
		}
	}
}
 
	static class Pair {
		int a, b;
 
		public Pair(int a1, int b1) {
			a = a1;
			b = b1;
 
		}
	}

    	
    	  	 	static class SegmentTree{
    	   	 		String[] arr , sTree;
    	   	 	static	int N;
    	   	 		public SegmentTree(String[] in){
    	   	 			arr=in;
    	   	 		N=arr.length-1;
    	   	 			sTree=new String[2*N];
    	   	 			
    	   	 			build(1,1,N);
    	   	 		}
    	   	 		public void build(int node, int l, int r){
    	   	 			if(l==r){
    	   	 				sTree[node]=arr[l];
    	   	 			}
    	   	 			else{
    	   	 				int leftchild=node*2;
    	   	 				int rightchild=node*2+1;
    	   	 				int mid =(l+r)/2;
    	   	 				build(leftchild,l,mid);
    	   	 				build(rightchild,mid+1,r);
    	   	 				sTree[node]=sTree[leftchild].concat(sTree[rightchild]);
    	   	 			}
    	   	 		}
    	   	 		public  void update(int i, String val){
    	   	 			int node =i+N-1;
    	   	 			arr[i]=val;
    	   	 			sTree[node]=val;
    	   	 			node=node/2;
    	   	 			while(node>0){
    	   	 			int leftchild=node *2;
       	 				int rightchild=node*2+1;
       	 			sTree[node]=sTree[leftchild].concat(sTree[rightchild]);
       	 			node=node/2;
    	   	 			}
    	   	 			return;
    	   	 			
    	   	 		}
    	   	 		public String query(int i, int j){
    	   	 			 return query(1,1, N,  i, j);
    	   	 		}
    	   	 		public String query(int node,int l, int r, int i , int j){
    	   	 			if(i>r||j<l){
    	   	 				return "";
    	   	 			}
    	   	 			if(i<=l&&r<=j){
    	   	 				return sTree[node];
    	   	 			}
    	   	 		int leftchild=node*2;
    	 				int rightchild=node*2+1;
    	 				int mid =(l+r)/2;
    	 				
    	 			return	(query(leftchild,l,mid,i,j).concat(query(rightchild,mid+1,r,i,j)));
    	 				
    	   	 		}
    	   	 	}
     
    	  	 	static ArrayList<Pair>factors;
    	    	static boolean isComposite[];
    	    	static ArrayList<Integer> primes;
    	    	public static boolean isprime(long n){
    	    		if(n<=10001){
    	    			return !isComposite[(int)n];
    	    		}
    	    		for(int i=0;i<primes.size();i++){
    	    			if(primes.get(i)*primes.get(i)*1l>n){
    	    				break;
    	    			}
    	    			if(n%primes.get(i)==0){
    	    				return false;
    	    			}
    	    			
    	    		}
    	    		return true;
    	    	}
    	    	
    	    	
    	    	public static void sieve(int n){
    	    		isComposite=new boolean[n+1];
    	    		primes =new ArrayList<Integer>();
    	    		isComposite[0]=true;
    	    		isComposite[1]=true;
    	    		for(int i=2;i<=n;i++){
    	    			if(!isComposite[i]){
    	    				for(int j=2*i;j<=n;j=j+i){
    	    					isComposite[j]=true;
    	    				}
    	    			}
    	    			primes.add(i);
    	    		}
    	    		
    	    	}
    	    	public static void primefactors(long n){
    	    		 factors=new ArrayList<Pair>();
    	    		for(int x:primes){
    	    			if(x*x*1l>n){
    	    				break;
    	    			}
    	    		
    	    			
    	    			if(n%x==0){
    	    				
    	    					Pair p=new Pair(x,0);
    	    					 factors.add(p);
    	    				while(n%x==0){
    	    				n/=x;
    	    				p.b++;}
    	    				
    	    			}
    	    		}
    	    		if(n!=1){
    	    			factors.add(new Pair((int)n,1));
    	    		}
    	    		
    	    	}
    	    	public static long powfact(long n,long p){
    	    		int res=0;
    	    		for(long i=p;i*1l<=n;i=i*p*1l){
    	    			res+=(n/i);
    	    		}
    	    		return res;
    	    	}
    	    	
    	    	public static long GCD(long i, long j){
    	    	if (i==0){
    	    		return j;
    	    	}
    	    	return GCD(j%i,i);
    	    	}
    	    	public static long LCM(long i, long j){
    	    		return(i*j)/GCD(i,j);
    	    	}
    	    
 	static class Scanner {
    		StringTokenizer st;
    		BufferedReader br;
     
    		public Scanner(InputStream s) {
    			br = new BufferedReader(new InputStreamReader(s));
    		}
     
    		public boolean hasNext() {
    			// TODO Auto-generated method stub
    			return false;
    		}
     
    		public String next() throws IOException {
    			while (st == null || !st.hasMoreTokens())
    				st = new StringTokenizer(br.readLine());
    			return st.nextToken();
    		}
     
    		public int nextInt() throws IOException {
    			return Integer.parseInt(next());
    		}
     
    		public long nextLong() throws IOException {
    			return Long.parseLong(next());
    		}
     
    		public String nextLine() throws IOException {
    			return br.readLine();
    		}
     
    		public double nextDouble() throws IOException {
    			String x = next();
    			StringBuilder sb = new StringBuilder("0");
    			double res = 0, f = 1;
    			boolean dec = false, neg = false;
    			int start = 0;
    			if (x.charAt(0) == '-') {
    				neg = true;
    				start++;
    			}
    			for (int i = start; i < x.length(); i++)
    				if (x.charAt(i) == '.') {
    					res = Long.parseLong(sb.toString());
    					sb = new StringBuilder("0");
    					dec = true;
    				} else {
    					sb.append(x.charAt(i));
    					if (dec)
    						f *= 10;
    				}
    			res += Long.parseLong(sb.toString()) / f;
    			return res * (neg ? -1 : 1);
    		}
     
    		public boolean ready() throws IOException {
    			return br.ready();
    		}
     
    	}}
