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.lang.*;
import java.io.*;

public class First {

	public static void main(String[] args) throws Exception {

//			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//			int t = Integer.parseInt(br.readLine());
//			StringBuilder sb = new StringBuilder();
//			while (t-- > 0) {
//				int n = Integer.parseInt(br.readLine());
//				String[] str = (br.readLine()).trim().split(" ");
//				int[] arr = new int[n];
//				for (int i = 0; i < n; i++) {
//					arr[i] = Integer.parseInt(str[i]);
//				}
//			}
//			return;

//		first();
//		sec();
		third();
//		four();
//			fif();
//			six();
	}

	private static void first() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();

		while (t-- > 0) {
			String[] str = (br.readLine()).trim().split(" ");
			int n = Integer.parseInt(str[0]);
			int x = Integer.parseInt(str[1]);
			int[] arr = new int[n];
			str = (br.readLine()).trim().split(" ");
			for (int i = 0; i < n; i++) {
				arr[i] = Integer.parseInt(str[i]);
			}
			str = (br.readLine()).trim().split(" ");
			int[] brr = new int[n];
			for (int i = 0; i < n; i++) {
				brr[i] = Integer.parseInt(str[i]);
			}
			if (t > 0)
				str = (br.readLine()).trim().split(" ");
			boolean can = true;
			for (int i = 0; i < n; i++) {
				if (arr[i] + brr[n - 1 - i] > x) {
					can = false;
					break;
				}
			}
			if (can) {
				System.out.println("Yes");
			} else {
				System.out.println("No");
			}

		}
		return;
	}

	private static void sec() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();

		while (t-- > 0) {
			String[] str = (br.readLine()).trim().split(" ");
			int a = Integer.parseInt(str[0]);
			int b = Integer.parseInt(str[1]);
			int c = Integer.parseInt(str[2]);
			int d = Integer.parseInt(str[3]);
			sb.append(Math.max(a + b, c + d) + "\n");
		}
		System.out.print(sb);
		return;
	}

	private static void third() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();

		while (t-- > 0) {
			String[] str = (br.readLine()).trim().split(" ");
			long p = Long.parseLong(str[0]);
			long q = Long.parseLong(str[1]);
			if (p < q || p % q != 0) {
				System.out.println(p);
			} else {
				HashMap<Long, Long> map = new HashMap<>();
				long count = 0;
				for (long i = 2; i *i<=(q); i++) {
					
					while (q % i == 0) {
						q /= i;
						count += 1;
					}
					if (count > 0) {
						map.put(i, count);
					}
					count = 0;
				}
				if (q >= 2) {
					map.put(q, 1l);
				}
				long max = 1l;
				for (long div : map.keySet()) {
					long freq = map.get(div);
					long temp = p;
					while (temp % div == 0) {
						temp /= div;
					}
					temp = (temp * (long) Math.pow(div, freq - 1));
					max = Math.max(temp, max);
				}
				System.out.println(max);
			}
		}
		return;
	}

	private static void four() throws Exception {
		System.out.println("four");
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();

		while (t-- > 0) {
			String[] str = (br.readLine()).trim().split(" ");
			long p = Long.parseLong(str[0]);
			long q = Long.parseLong(str[1]);
			if (p < q || p % q != 0) {
				System.out.println(p);
			} else {
				long ans = 0;
				if (q <= Math.sqrt(p)) {
					for (long i = 2; i <= Math.sqrt(p); i++) {
						if (q % i == 0) {
							ans = p / i;
							if (ans % q != 0) {
								break;
							}
						}
					}
				}
				System.out.println(ans);
			}
		}
		return;
	}

	private static void fif() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();

		while (t-- > 0) {
			int n = Integer.parseInt(br.readLine());
			String[] str = (br.readLine()).trim().split(" ");
			int[] arr = new int[n];
			for (int i = 0; i < n; i++) {
				arr[i] = Integer.parseInt(str[i]);
			}
		}
		return;
	}

	private static void six() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();

		while (t-- > 0) {
			int n = Integer.parseInt(br.readLine());
			String[] str = (br.readLine()).trim().split(" ");
			int[] arr = new int[n];
			for (int i = 0; i < n; i++) {
				arr[i] = Integer.parseInt(str[i]);
			}
		}
		return;
	}
}
