3986: 因子化简

小 P 同学在学习了素数的概念后得知，任意的正整数 n 都可以唯一地表示为若干素因子相乘的形式。如果正整数 n 有 m 个不同的素数因子 p₁, p₂, ..., pₘ，则可以表示为：n = p₁^t₁ × p₂^t₂ × ... × pₘ^t。 小 P 认为，每个素因子对应的指数 tᵢ 反映了该素因子对于 n 的重要程度。现设定一个阈值 k，如果某个素因子 pᵢ 对应的指数 t 小于 k，则认为该素因子不重要，可以将 pᵢ^tᵢ 项从 n 中除去；反之则将 pᵢ^tᵢ 项保留。最终剩余项的乘积就是 n 简化后的值，如果没有剩余项则认为简化后的值等于 1。 试编写程序处理 q 个查询： - 每个查询包含两个正整数 n 和 k，要求计算按上述方法将 n 简化后的值。

从标准输入读入数据。 输入共 q + 1 行。 输入第一行包含一个正整数 q，表示查询的个数。 接下来 q 行每行包含两个正整数 n 和 k，表示一个查询。

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

3
2155895064 3
2 2
10000000000 10

2238728
1
1000000000