Description

给定两个正整数 $n,k$，其中 $k\ge 3$，求最大的 $p$ 使得 $p^k$ 是 $n$ 的因数。

数据保证 $k$ 在 $3\sim 30$ 之间均匀随机生成，但 $n$ 的取值可能会基于 $k$。

Input Format

本题多测。

第一行，一个正整数 $T$，表示数据组数。

随后输入 $T$ 组数据。对于每组数据，输入两个正整数 $n,k$。

Output Format

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

5
8 3
256 3
81 4
648 4
1296 5

2
4
3
3
1

Hint

样例二

见下发文件下的 nogame2.in 与 nogame2.ans。

该样例约束与测试点 $1$ 一致。

数据范围

对于测试点编号为奇数的测试点，$n$ 在指定范围内均匀随机生成。

对于所有数据，保证 $100\le T\le 10^6$，$1\le n\le 2^{60}$，$3\le k\le 30$，$k$ 在指定范围内均匀随机生成。

提示

本题输入输出规模较大，请使用较为快速的输入输出方式。