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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class CF {
	
	private static FS sc = new FS();
	
	private static class FS {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());				               
	            } catch (IOException e) {}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		long nextLong() {
			return Long.parseLong(next());
		}
	}
	
	private static class extra {
		
		static int[] intArr(int size) {
			int[] a = new int[size];
			for(int i = 0; i < size; i++) a[i] = sc.nextInt();
			return a;
		}
		
		static long[] longArr(int size) {
			long[] a = new long[size];
			for(int i = 0; i < size; i++) a[i] = sc.nextLong();
			return a;
		}
		
		static long intSum(int[] a) {
			long sum = 0; 
			for(int i = 0; i < a.length; i++) {
				sum += a[i];
			}
			return sum;
		}
		
		static long longSum(long[] a) {
			long sum = 0; 
			for(int i = 0; i < a.length; i++) {
				sum += a[i];
			}
			return sum;
		}
		
	}
	
	public static void main(String[] args) {
		
		int t = sc.nextInt();
//		int t = 1;
		StringBuilder ret = new StringBuilder();
		while(t-- > 0) {
			long p = sc.nextLong();
			int q = sc.nextInt();
			HashSet<Integer> temp = factor(q);
			long max = 0;
			for(int aa:temp) {
				long now = p;
				while(now%q == 0 && now != 0) { 
					now /= aa;
				}
				if(max < now) {
					max = now;
				}
			}
			ret.append(max + "\n");
		}
		System.out.println(ret);
	}
	
	static HashSet<Integer> factor(int q) {
		HashSet<Integer> temp = new HashSet<>();
		int sqrt = (int)Math.sqrt(q);
		while(q%2 == 0) {
			temp.add(2);
			q /= 2;
		}
		for(int i = 3; i <= sqrt; i += 2) {
			while(q%i == 0) {
				temp.add(i);
				q /= i;
			}
		}
		if(q > 2) temp.add(q);
		return temp;
	}
	
}
