说明

ykw 最近很喜欢玩成语接龙，有一天他突发奇想

能不能和小伙伴玩一个数字接龙？

他决定尝试设计一种有趣的数字接龙，规则如下：

有 $n$ 个合数，每个数都可以被表示成 $x = p * q$ 的形式($p,q$为两个互异质数)

若 $a = p1 * q1, b = p2 * q2$ 满足 $p1 < q1, p2 < q2, q1 == p2$ 时候 ykw 认为 $b$ 可以接在 $a$ 的后面

现在 ykw 想知道这 $n$ 个数字中最多能选出几个数字成为一个接龙序列？

输入格式

输入第一行包含一个正整数 $n$，表示数字个数

输入第二行包含 $n$ 个合数 $a_1, a_2 \dots a_n$。

对于 $30\%$ 的数据满足：$n \leq 10, a_i \leq 1000$

对于 $60\%$ 的数据满足：$n \leq 1000, a_i \leq 10^6$

对于 $100\%$ 的数据满足：$n \leq 50000, a_i \leq 10^6$

输出格式

输出一行，表示最多能选出的数字个数。

样例

9
10 6 22 15 21 35 77 119 187

5

提示

最长接龙序列为 $6,15,35,77,187$