题目描述

小A同学发明了一种神奇序列，这种序列的定义是，一个正整数序列，其中任意两个相邻元素都不互质（即拥有1以外的公因子），现在小A获得了一个正整数序列，他希望能找到该序列中最长的一个子序列，并使其为一个神奇序列。

文件输入

第一行一个正整数n，表示序列的长度 接下来一行n个正整数，分别表示序列的n个元素，序列的第i个元素为$a_i$

文件输出

输出给定的序列中能找到的最长的神奇序列长度

输入样例

5
2 2 2 2 2

输出样例

5

数据规模

对于前20%的数据，$n<=100$，$a_i \le 1000$ 对于前40%的数据，$n<=1000$，$a_i \le 10000$ 对于前60%的数据，$n<=5000$，$ai \le 100000$ 对于前100%的数据，$n<=100000$，$ai \le 1000000$