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.util.*;
public class n1{
	static PrintWriter out=new PrintWriter(System.out);
	static int[]primes=goodSieve(50000);
	public static void main(String[] args) throws Exception{
		int t=I.readInt();
		for(int i=0;i<t;i++){
			solve();
		}
	}
	public static long pow(long b,long e) {
		long ans=1;
		for(int i=0;i<e;i++) {
			ans*=b;
		}
		return ans;
	}
	public static void solve() throws Exception{
		long p=I.readLong();
		long q=I.readLong();
//		System.out.println(p+" "+q);
		if(p%q!=0){
			System.out.println(p);
			return;
		}
		long best=1;
		long rem=q;
		for(long prime:primes) {
			if(q%prime==0) {
				int count=0;
				long q2=q;
				while(q2%prime==0) {
					q2/=prime;
					count++;
				}
				long cand=pow(prime,count-1);
				rem/=(cand*prime);
				if(p%cand==0) {
					long p2=p;
					while(p2%prime==0) {
						p2/=prime;
					}
					cand*=p2;
					if(cand>best) {
						best=cand;
					}
				}
			}
		}
		long best2=1;
		if(rem!=1) {
			while(p%rem==0) {
				p/=rem;
			}
			if(p>best) {
				System.out.println(p);
				return;
			}
		}
		System.out.println(best);
	}

	public static int[] goodSieve(int len){//Kar lepo zoptimiziran. 
		boolean[] prime=new boolean[len];
		Arrays.fill(prime,true);
		prime[0]=false;
		prime[1]=false;
		for(int i=2;i*i<len;i++){
			if(prime[i]){
				for(int j=2*i;j<len;j+=i){
					prime[j]=false;
				}
			}
		}
		int t=0;
		for(boolean b:prime){
			if(b){
				t++;
			}
		}
		int[] ans=new int[t];
		t=0;
		for(int i=0;i<prime.length;i++){
			if(prime[i]){
				ans[t++]=i;
			}
		}
		return ans;
	}

}

class I{
	static BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	public static String nextToken() throws Exception{
		while(st==null||!st.hasMoreTokens()){
			st=new StringTokenizer(in.readLine(),"[ ,:]");
		}
		return st.nextToken();
	}
	public static int readInt() throws Exception{
		return Integer.parseInt(nextToken());
	}
	public static long readLong() throws Exception{
		return Long.parseLong(nextToken());
	}
	public static double readDouble() throws Exception{
		return Double.parseDouble(nextToken());
	}
	public static String readString() throws Exception{
		return nextToken();
	}
	public static String readLine() throws Exception{
		return in.readLine();
	}
}

class tocka{
	int x,y;
	tocka(int a,int b){
		x=a;
		y=b;
	}

	@Override public String toString(){
		return "tocka [p="+x+", q="+y+"]";
	}

}