等我成功了,我们一起分蛋糕!
— 顺
西蒙斯有 $$$n$$$ 朋友和大量蛋糕。为了公平地分配蛋糕,请你帮助他解决以下问题:
- 求最小值 积极 整数$$$k$$$,使得$$$n$$$ 是$$$k^n$$$ 的除数。
可以证明,在给定的约束条件下,答案总是存在。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。
每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$2\le n\le 10^9$$$) — Simons 的朋友数量。
输出
对于每个测试用例,输出一个整数 - 您找到的最小 $$$k$$$。
示例
输入复制
481236955635800
输出复制
261232090
注意
在第一个测试用例中:
- $$$1^8=1$$$,且 $$$8$$$ 不是 $$$1$$$ 的约数;
- $$$2^8=256$$$,$$$8$$$ 是 $$$256$$$ 的除数,因为 $$$256 = 8\cdot 32$$$。
因此,最小可能的 $$$k$$$ 是 $$$2$$$。
在第二个测试用例中,$$$12$$$ 是 $$$6^{12}=2\,176\,782\,336$$$ 的除数,因为 $$$2\,176\,782\,336=12\cdot 181\,398\,528$$$。