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.
//189301019.akshay
import java.io.BufferedReader; 
import java.io.IOException; 
import java.io.InputStreamReader; 
import java.util.Scanner;
import java.util.Set;
import java.util.Random;
import java.util.Arrays;
import java.util.StringTokenizer; 
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Collections;

public class C 
{ 
	
    public static void main(String[] args) 
	{ 
		FastReader sc=new FastReader(); 
		StringBuffer ans=new StringBuffer();
		int test=sc.nextInt();
		while(test-->0)
		{
			long p=sc.nextLong();
			long q=sc.nextLong();
			if(p%q != 0) {
				ans.append(p+"\n");
				continue;
			}
			if(p == q) {
				
				long x=getLargestFactor(p);
				
				ans.append(x+"\n");
				continue;
			}
			HashMap<Long,Long> map=getFactors(q);
			long maxm = 1;
//			for(long x:set) {
//				long temp=(long)p;
//				while(temp%x == 0) {
//					temp/=x;
//				}
//				if(temp>maxm)
//					maxm=temp;
//			}
			
			Set<Long> keys = map.keySet();
//			System.out.println(map);
			for(long x:keys) {
				long temp = p;
				while(temp%x == 0) {
					temp/=x;
				}
				temp=temp*binpow(x,map.get(x)-1);
				if(temp>maxm)maxm=temp;
			}
			
			ans.append(maxm+"\n");
		}
		
	    System.out.print(ans);
	} 
    static long binpow(long a,long b) {
    	if(b == 0) return 1;
    	long temp = binpow(a,b/2);
    	temp*=temp;
    	if(b%2 != 0)
    		temp*=a;
    	return temp;
    }
    
    static HashMap<Long,Long> getFactors(long n){
    	HashMap<Long,Long> primes=new HashMap<>();
    	
    	for(long i=2;i*i<=n;i++) {
    		if(n%i != 0)continue;
    		long cnt=0;
    		while(n%i == 0) {
    			++cnt;
    			n/=i;
    		}
    		primes.put(i,cnt);
    	}
    	if(n>1)
    		primes.put(n,1l);
    	return primes;
    }
    
    static long getLargestFactor(long x) {
    	if(x%2 == 0) return x/2;
    	
    	long maxm=1;
    	
    	for(long i=2;i*i<=x;i++) {
    		if(x%i == 0) {
    			
    			long a=i;
    			long b=x/i;
    			
    			if(a>b) return a;
    			return b;
    			
    		}
    	}
    
    	return 1l;
    }
    
    static final Random random=new Random();
    
	static void ruffleSort(int[] a) {
		int n=a.length;//shuffle, then sort 
		for (int i=0; i<n; i++) {
			int oi=random.nextInt(n), temp=a[oi];
			a[oi]=a[i]; a[i]=temp;
		}
		Arrays.sort(a);
	}
	
	static void ruffleSort(long[] a) {
		int n=a.length;//shuffle, then sort 
		for (int i=0; i<n; i++) {
			int oi=random.nextInt(n);
			long temp=a[oi];
			a[oi]=a[i]; a[i]=temp;
		}
		Arrays.sort(a);
	}
	
	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; 
		} 
	} 


} 
