题目描述

小$\red{Y}$酷爱的接龙游戏正是这样。玩腻了成语接龙之后，小$\red{Y}$决定尝试无平方因子二元合数接龙，规则如下：

现有$\red{n}$个不超过$\red{10^6}$的合数，每个均可表示为$\red{a=p\times q(p,q}$为两个互异素数$\red{)}$。

若$\red{a=p_1\times q_1(p_1<q_1),b=p_2\times q_2(p_2<q_2)，}$当且仅当$\red{q_1=p_2}$时$\red{b}$能接在$\red{a}$后面。

请问从给定的这 个数中选数接龙，最长可以形成一个包含多少数的接龙序列？

输入格式

第一行输入一个正整数 $\red{n，}$意义如题干所述。（$\red{n≤}$$\red{50000）}$

第二行输入 $\red{n }$个不超过 $\red{10^6 }$的合数。

输出格式

输出仅一个整数，表示问题的答案。

样例

输入样例

9
10 6 22 15 21 35 77 119 187

输出样例

5

提示

样例解释

最长接龙为$\red{\{6(2\times 3),15(3\times 5),35(5\times 7),77(7\times 11),187(11\times 17)\}，}$长度为$\red{5}$。

测试点$\red{1\sim 3}$满足：$\red{n=9，}$每个数不超过$\red{1000}$;

测试点$\red{4\sim 6}$满足：$\red{n=1000，}$每个数不超过$\red{10^6}$;

测试点$\red{7\sim 10}$满足：$\red{n=50000，}$每个数不超过$\red{10^6}$;