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 static java.lang.Math.*;

import java.util.*;

public class A {

	public Object solve () {
		long P = sc.nextLong(), Q = sc.nextLong();

		if (P % Q != 0)
			return P;

		long [][] A = primeFactorization(Q);
		long res = 0;

		for (long [] a : A) {
			long X = P;
			while (X % Q == 0)
				X /= a[0];
			res = max(res, X);
		}

		return res;
	}

	private static final int CONTEST_TYPE = 2;

	private static void init() {
	}

	private static long[][] primeFactorization(long N) {
		List<long[]> res = new ArrayList<long[]>();
		if (N % 2 == 0) {
			long[] r = { 2, 0 };
			while (N % 2 == 0) {
				++r[1];
				N /= 2;
			}
			res.add(r);
		}
		for (long p = 3; p * p <= N; p += 2)
			if (N % p == 0) {
				long[] r = { p, 0 };
				while (N % p == 0) {
					++r[1];
					N /= p;
				}
				res.add(r);
			}
		if (N > 1)
			res.add(new long[] { N, 1 });
		return res.toArray(new long[0][]);
	}

	//////////////////////////////////////////////////////////////////////////////////// OFF
	private static IOUtils.MyScanner sc = new IOUtils.MyScanner();

	private static class IOUtils {
		public static class MyScanner {
			public String next() {
				newLine();
				return line[index++];
			}

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

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

			//////////////////////////////////////////////
			private boolean eol() {
				return index == line.length;
			}

			private String readLine() {
				try {
					return r.readLine();
				} catch (Exception e) {
					throw new Error(e);
				}
			}

			private final java.io.BufferedReader r;

			private MyScanner() {
				this(new java.io.BufferedReader(new java.io.InputStreamReader(System.in)));
			}

			private MyScanner(java.io.BufferedReader r) {
				try {
					this.r = r;
					while (!r.ready())
						Thread.sleep(1);
					start();
				} catch (Exception e) {
					throw new Error(e);
				}
			}

			private String[] line;
			private int index;

			private void newLine() {
				if (line == null || eol()) {
					line = split(readLine());
					index = 0;
				}
			}

			private String[] split(String s) {
				return s.length() > 0 ? s.split(" ") : new String[0];
			}
		}

		private static String build(Object o, Object... A) {
			return buildDelim(" ", o, A);
		}

		private static String buildDelim(String delim, Object o, Object... A) {
			StringBuilder b = new StringBuilder();
			append(b, o, delim);
			for (Object p : A)
				append(b, p, delim);
			return b.substring(min(b.length(), delim.length()));
		}

		//////////////////////////////////////////////////////////////////////////////////
		private static java.text.DecimalFormat formatter = new java.text.DecimalFormat("#.#########");

		private static void start() {
			if (t == 0)
				t = millis();
		}

		private static void append(java.util.function.Consumer<Object> f, java.util.function.Consumer<Object> g,
				final Object o) {
			if (o.getClass().isArray()) {
				int len = java.lang.reflect.Array.getLength(o);
				for (int i = 0; i < len; ++i)
					f.accept(java.lang.reflect.Array.get(o, i));
			} else if (o instanceof Iterable<?>)
				((Iterable<?>) o).forEach(f::accept);
			else
				g.accept(o instanceof Double ? formatter.format(o) : o);
		}

		private static void append(final StringBuilder b, Object o, final String delim) {
			append(x -> {
				append(b, x, delim);
			}, x -> b.append(delim).append(x), o);
		}

		private static java.io.PrintWriter pw = new java.io.PrintWriter(System.out);

		private static void print(Object o, Object... A) {
			String res = build(o, A);
			if (DEBUG == 2)
				err(res, '(', time(), ')');
			if (res.length() > 0)
				pw.println(res);
			if (DEBUG == 1) {
				pw.flush();
				System.out.flush();
			}
		}

		private static void err(Object o, Object... A) {
			System.err.println(build(o, A));
		}

		private static int DEBUG;

		private static void exit() {
			String end = "------------------" + System.lineSeparator() + time();
			switch (DEBUG) {
			case 1:
				print(end);
				break;
			case 2:
				err(end);
				break;
			}
			IOUtils.pw.close();
			System.out.flush();
			System.exit(0);
		}

		private static long t;

		private static long millis() {
			return System.currentTimeMillis();
		}

		private static String time() {
			return "Time: " + (millis() - t) / 1000.0;
		}

		private static void run(int N) {
			try {
				DEBUG = Integer.parseInt(System.getProperties().get("DEBUG").toString());
			} catch (Throwable t) {
			}

			for (int n = 1; n <= N; ++n) {
				Object res = new A().solve();
				if (res != null) {
					@SuppressWarnings("all")
					Object o = CONTEST_TYPE == 0 ? "Case #" + n + ": " + build(res) : res;
					print(o);
				}
			}
			exit();
		}
	}

	////////////////////////////////////////////////////////////////////////////////////
	public static void main(String[] args) {
		init();
		@SuppressWarnings("all")
		int N = CONTEST_TYPE == 1 ? 1 : sc.nextInt();
		IOUtils.run(N);
	}
}
