#1184. 「AHOI 2018 初中组」根式化简

「AHOI 2018 初中组」根式化简

题目描述

小可可在学习「立方根」的知识时碰到了这样的问题。

将下面根式化简为最简根式:

  1. 1253\sqrt[3]{125}
  2. 813\sqrt[3]{81}
  3. 523\sqrt[3]{52}

这个问题对于小可可来说太简单了,他很快就算出了答案:

  1. 55
  2. 3333\sqrt[3]{3}
  3. 523\sqrt[3]{52}

小可可知道任意形如 x3\sqrt[3]{x} 的根式,化简后一定可以被写成形如 ab3a\sqrt[3]{b} ​的最简根式。他觉得这很有趣,就仿照出了不少题,但没一会儿就被密密麻麻的根式绕晕了,于是他向你求助:

给定 nn 个形如 x3\sqrt[3]{x} 的根式,请你将它们化简为形如 ab3a\sqrt[3]{b} 的最简形式,为了方便,你只需要输出其中的 aa 即可。

如果你没有学过这部分数学知识,你可以认为题意是:给你 nn 个正整数 xx,对于每一个 xx,你需要求出整数 a,ba,b 使得 a3×b=xa^3 \times b = x,输出最大的整数 aa 即可。

输入格式

输入有两行:

第一行一个整数 nn,表示有 nn 个形如 x3\sqrt[3]{x} 的根式;

第二行 nn 个正整数,依次给出每个 xx

输出格式

输出 nn 行,每行一个正整数,第 ii 行正整数表示你对输入中第 iixx 给出的答案。

样例

3
125 81 52
5
3
1

数据范围与提示

测试点编号 nn xx
1,21,2 n10n\le 10 x106x\le 10^6
3,43,4 x109x\le 10^9
5,65,6 n100n\le 100 x1018x\le 10^{18}xx 为完全立方数
7,87,8 n500n\le 500 x1018x\le 10^{18}
9,109,10 n104n\le 10^4