问题描述

质数（素数）是大于 $1$ 的自然数中，除了 $1$ 与它本身外没有其他因数的数。任意正整数 $n$ 都可以唯一分解为若干素因子的乘积。若不同素因子为 $p_1,p_2,\dots,p_m$，对应的指数为 $t_1,t_2,\dots,t_m$，则

$$n = p_1^{t_1}\times p_2^{t_2}\times\cdots\times p_m^{t_m}. $$

小 $P$ 认为若某个素因子 $p_i$ 的指数 $t_i$ 小于阈值 $k$，则该素因子不重要，可以将对应的 $p_i^{t_i}$ 从 $n$ 中除去；否则保留该项。经过处理后剩下的乘积即为 $n$ 的简化值；若所有项都被除去，则简化结果为 $1$。

给定 $q$ 个查询，每个查询给出一对正整数 $n$ 和 $k$，请计算对应的简化结果。

输入格式

第一行包含一个正整数 $q$，表示查询个数。 接下来 $q$ 行，每行包含两个正整数 $n$ 和 $k$，表示一次查询。

• $1 < n \le 10^{10}$。
• $1 < k, q \le 10$。

输出格式

输出共 $q$ 行。第 $i$ 行输出对应第 $i$ 个查询的简化结果（一个正整数）。

样例输入

3
2155895064 3
2 2
10000000000 10

样例输出

2238728
1
10000000000

说明

样例解释

• 查询 $1$： $2155895064 = 2^3 \times 3^2 \times 23^4 \times 107^1$。当 $k=3$ 时，保留指数 $\ge 3$ 的素因子，只有 $2^3$ 与 $23^4$ 被保留，结果为 $2^3\times23^4=2238728$。

• 查询 $2$： $n=2$，若 $k=2$ 则指数 $1<2$ 被去掉，结果为 $1$。

• 查询 $3$： $n=10^{10}$，若 $k=10$ 则所有素因子的指数均不小于 $10$（若分解后满足），在此样例中按题给出的分解全部保留，结果仍为 $10000000000$。