题目背景

洛谷的测试数据仅供民间交流使用，非官方测试数据。官方评测链接：https://www.cspro.org/。

题目描述

质数（又称“素数”）是指在大于 $1$ 的自然数中，除了 $1$ 和它本身以外不再有其他因数的自然数。

小 P 同学在学习了素数的概念后得知，任意的正整数 $n$ 都可以唯一地表示为若干素因子相乘的形式。如果正整数 $n$ 有 $m$ 个不同的素数因子 $p_1, p_2, \cdots, p_m$，则可以表示为：$n = p_1^{t_1} \times p_2^{t_2} \times \cdots \times p_m^{t_m}$。

小 P 认为，每个素因子对应的指数 $t_i$ 反映了该素因子对于 $n$ 的重要程度。现设定一个阈值 $k$，如果某个素因子 $p_i$ 对应的指数 $t_i$ 小于 $k$，则认为该素因子不重要，可以将 $p_i^{t_i}$ 项从 $n$ 中除去；反之则将 $p_i^{t_i}$ 项保留。最终剩余项的乘积就是 $n$ 简化后的值，如果没有剩余项则认为简化后的值等于 $1$。

试编写程序处理 $q$ 个查询：

• 每个查询包含两个正整数 $n$ 和 $k$，要求计算按上述方法将 $n$ 简化后的值。

输入格式

从标准输入读入数据。

输入共 $q + 1$ 行。

输入第一行包含一个正整数 $q$，表示查询的个数。

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

输出格式

输出到标准输出。

输出共 $q$ 行。

每行输出一个正整数，表示对应查询的结果。

3
2155895064 3
2 2
10000000000 10

2238728
1
10000000000

提示

样例解释

查询一：

• $n = 2^3 \times 3^2 \times 23^4 \times 107$
• 其中素因子 $3$ 指数为 $2$，$107$ 指数为 $1$。将这两项从 $n$ 中除去后，剩余项的乘积为 $2^3 \times 23^4 = 2238728$。

查询二：

• 所有项均被除去，输出 $1$。

查询三：

• 所有项均保留，将 $n$ 原样输出。

子任务

$40\%$ 的测试数据满足：$n \le 1000$；

$80\%$ 的测试数据满足：$n \le 10^5$；

全部的测试数据满足：$1 < n \le 10^{10}$ 且 $1 < k, q \le 10$。