Zztrans' Math

题号：NC221061
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

给定 n 个数 $a_1,a_2,\cdots,a_n$ ，保证每个数都可以写成 $a_i = p\times q$ (p,q 都不是合数）的形式。

现在，Zztrans 想要从中选出 k 个下标 $i_1,i_2,\cdots,i_k$ $(i_1\lt i_2 \lt \cdots \lt i_k)$ ，使得 $a_{i_1},a_{i_2},\cdots,a_{i_k}$ 中任选两个数都互质。

这个问题被 Compute 秒了，所以他想问问你，这个 k 最大可以为多少？

输入描述:

第一行有一个整数 n 。

第二行有 n 个整数  ，保证  (p, q都不是合数)。

输出描述:

在一行输出一个整数 k，表示最多可以选出的满足要求的数的个数。

示例1

输入

复制

6
21 4 2 6 10 15

输出

复制

说明

样例中符合条件的选法是：
{21, 4}, {21, 2}, {21, 10}, {4, 15}, {2, 15} 。

可以发现，没有 k = 3 的情况符合。

备注:

一个数是合数当且仅当它能被除了 1 和它本身的其他整数整除。