酷爱接龙游戏的小 Y 决定尝试无平方因子二元合数接龙，规则如下：现有 n 个不超过 10^6 的合数，每个均可表示为 a = p*q（p、q 为两个互异素数，且 p < q）。若 a = p_1*q_1，b = p_2*q_2（p_1 < q_1，p_2 < q_2），当且仅当 q_1 = p_2 时，b 能接在 a 后面。请问从给定的这 n 个数中选数接龙，最长可以形成一个包含多少数的接龙序列？

1. 第一行输入一个正整数 n（n \leq 50000）。

2. 第二行输入 n 个不超过 10^6 的合数。

输出仅一个整数，表示最长接龙序列的长度。

- 测试点 1∼3：n = 9，每个数不超过 1000；

- 测试点 4∼6：n = 1000，每个数不超过 10^6；

- 测试点 7∼10：n = 50000，每个数不超过 10^6。

样例解释

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