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.util.*;
import java.math.BigInteger;  
import java.io.*;
public class A {
	static void primeFactors(long n , HashMap<Long, Long> hmap) {
		while(n%2==0) {
			n=n/2;
			hmap.put(2L, hmap.getOrDefault(2L, 0L)+1);
		}
		for(long i=3;i<=Math.sqrt(n);i=i+2) {
			while(n%i==0) {
				n=n/i;
				hmap.put(i, hmap.getOrDefault(i, 0L)+1);
			}
		}
		if(n>2)
			hmap.put(n, hmap.getOrDefault(n, 0L)+1);
	}
	public static void main(String args[]) {
		Scanner in=new Scanner(System.in);
		int t=in.nextInt();
		L: while(--t>=0) {
			long a=in.nextLong();
			long b=in.nextLong();
			long copy=a;			
			HashMap<Long, Long> hmap2=new HashMap<>();
			primeFactors(b, hmap2);
			
			HashMap<Long, Long> hmap1=new HashMap<>();
			for(long val: hmap2.keySet()) {
				while(a%val==0) {
					hmap1.put(val, hmap1.getOrDefault(val, 0L)+1);
					a=a/val;
				}
			}
//			System.out.println(hmap1);
//			System.out.println(hmap2);
			long min=Long.MAX_VALUE;
			for(long val: hmap2.keySet()) {
				if(!hmap1.containsKey(val) || hmap1.get(val)<hmap2.get(val)) {
					System.out.println(copy);
					continue L;
				}
				else {
					min=Math.min(min, BigInteger.valueOf(val).pow((int)(hmap1.get(val)-hmap2.get(val)+1)).longValue());
				}
			}
			System.out.println(copy/min);
		}
		
	}

	///////////////////////////
	static class FastScanner {
		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) {
					e.printStackTrace();
				}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		int[] nextArray(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}

		long nextLong() {
			return Long.parseLong(next());
		}
	}
}
