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.HashMap;
import java.util.List;
import java.util.Scanner;

public class Round680Div2ProbC {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner scn = new Scanner(System.in);
		int t = scn.nextInt();
		while (t > 0) {
			long p = scn.nextLong();
			long q = scn.nextLong();
			System.out.println(solve(p, q));
			t--;
		}
	}

	public static long solve(long p, long q) {
		if (p < q) {
			return p;
		}
		if (p % q != 0) {
			return p;
		}
		HashMap<Long, Long> map = new HashMap<>();
		factorize(q, map);
		long ans = Long.MIN_VALUE;
		for (long pf : map.keySet()) {
			long t = p;
			while (t % q == 0) {
				t = t / pf;
			}
			ans = Math.max(ans, t);
		}
		return ans;
	}

	static void factorize(long n, HashMap<Long, Long> map) {
		long count = 0;

		// count the number of times 2 divides
		while (!(n % 2 > 0)) {
			// equivalent to n=n/2;
			n >>= 1;

			count++;
		}

		// if 2 divides it
		if (count > 0) {
			map.put(2L, count);
		}

		// check for all the possible
		// numbers that can divide it
		for (long i = 3; i <= (long) Math.sqrt(n); i += 2) {
			count = 0;
			while (n % i == 0) {
				count++;
				n = n / i;
			}
			if (count > 0) {
				map.put(i, count);
			}
		}

		// if n at the end is a prime number.
		if (n > 2) {
			map.put(n, 1L);
		}
	}

	static void printDivisors(long n, List<Long> list) {
		// Note that this loop runs till square root
		for (long i = 1; i <= Math.sqrt(n); i++) {
			if (n % i == 0) {
				// If divisors are equal, print only one
				if (n / i == i)
					list.add(i);

				else // Otherwise print both
				{
					list.add(i);
					list.add(n / i);
				}
			}
		}
	}

}
