← 返回题目列表

Codeforces · 2205/B

B. 西蒙斯和蛋糕的成功

中文机器翻译题面 查看原题
等我成功了,我们一起分蛋糕!
— 顺

西蒙斯有 $$$n$$$ 朋友和大量蛋糕。为了公平地分配蛋糕,请你帮助他解决以下问题:

  • 求最小值 积极 整数$$$k$$$,使得$$$n$$$ 是$$$k^n$$$ 的除数。

可以证明,在给定的约束条件下,答案总是存在。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。

每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$2\le n\le 10^9$$$) — Simons 的朋友数量。

输出

对于每个测试用例,输出一个整数 - 您找到的最小 $$$k$$$。

示例

输入
复制

4
8
12
369
55635800

输出
复制

2
6
123
2090

注意

在第一个测试用例中:

  • $$$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$$$。