AT_oidashi_d.幾何問題を書こう

A君设计了一个几何问题，这个问题的答案通常是一个有理数。为了确保在这个问题中答案总是有理数，A君特意进行了一些改动。详细内容如下：

一个球体的体积为 $v$，现需要通过削去多余的部分来制作一个尽可能大的立方体。求出可以制作的最大立方体的一条边长，再乘以一个实数 $r$ 输出结果。可以确保答案一定是非零的有理数。

A君已经挑选出了 $n$ 个可能的测试用例，即 $v_1, v_2, \ldots, v_n$，但不知道如何选择适当的 $r$ 使得尽可能多的测试用例产生有理数答案。你需要帮助A君选择一个合适的 $r$，使得产生有理数答案的测试用例数量最多。请问最多可以使多少个测试用例的答案是有理数？

输入格式

• 第一行输入一个整数 $n$，表示候选体积的数量。
• 接下来的 $n$ 行，每行输入一个整数，表示体积 $v_i$。

输出格式

在一行中输出答案为有理数的测试用例数量的最大值。请勿忘记输出末尾的换行符。

数据范围与提示

• $n, v_i$ 均为整数。
• $1 \leq n \leq 30000$。
• $1 \leq v_i \leq 10^{12}$（$1 \leq i \leq n$）。

这个问题有部分分数：

• 若 $n \leq 2000$ 且 $v_i \leq 10^6$ 的情况下正确解决，非常有可能获得 98 分。
• 若无额外限制的情况下正确解决，总可能得到 100 分。

有理数是指可以表示为两个整数 $p$ 和非零整数 $q$ 的比值 $\frac{p}{q}$。在A君的问题中，答案不得为 $0$，因此 $r$ 不能为 $0$。

示例

输入：

4
1
1
125
8

输出：

4

例如，当 $r = \sqrt[6]{\frac{3\pi^2}{4}}$ 时，所有结果都是有理数。

输入：

3
4
32
1

输出：

2

例如，当 $r = \sqrt[6]{3\pi^2}$ 时，第一个和第二个答案是有理数。

输入：

20
90277606625
641956187000
1264908284352
91500888625
5856056872
722220853000
374787639808
1264908284352
220190972141
1264908284352
46848454976
533633182461
251078438387
5856056872
732007109000
158113535544
19764191943
1247997633984
974301462079
46848454976

输出：

15

本翻译由 AI 自动生成