P14949 游戏人生

我不要游戏。

给定两个正整数 $n,k$，其中 $k\ge 3$，求最大的 $p$ 使得 $p^k$ 是 $n$ 的因数。 **数据保证 $k$ 在 $3\sim 30$ 之间均匀随机生成，但 $n$ 的取值可能会基于 $k$。**

**本题多测。** 第一行，一个正整数 $T$，表示数据组数。 随后输入 $T$ 组数据。对于每组数据，输入两个正整数 $n,k$。

对于每组数据，输出一行一个整数 $p$。

### 样例二 见下发文件下的 `nogame2.in` 与 `nogame2.ans`。 该样例约束与测试点 $1$ 一致。 ### 数据范围 | 测试点编号 | $n\le $ | $T=$ | | :-: | :-: | :-: | | $1$ | $10^3$ | $10^3$ | | $2\sim 3$ | $10^7$ | $10^6$ | | $4\sim 5$ | $2^{60}$ | $100$ | | $6\sim 7$ | $2^{60}$ | $10^5$ | | $8\sim 10$ | $2^{60}$ | $10^6$ | 对于测试点编号为奇数的测试点，$n$ 在指定范围内均匀随机生成。 对于所有数据，保证 $100\le T\le 10^6$，$1\le n\le 2^{60}$，$3\le k\le 30$，$k$ 在指定范围内均匀随机生成。 ### 提示 **本题输入输出规模较大，请使用较为快速的输入输出方式。**