题目描述

现有一个长度为 $n$ 的序列，你需要从中选出一些数来，保持这些数在原来序列中的相对位置组成一个新的序列，使得相邻的两个元素不互质。输出新序列的最长长度。两个数不互质，它们的最大公约数应该大于 $1$。

输入格式

第一行一个整数 $n$，表示原序列的长度。
第二行 $n$ 个数，表示原序列的长度。

输出格式

输出新序列的最长长度，数据保证答案至少为 $2$。

样例 #1

样例输入 #1

7
2 3 4 5 6 7 8

样例输出 #1

4

数据范围与提示

对于 $20\%$ 的数据，所有输入数据的范围 $[1, 20]$；
对于 $40\%$ 的数据，所有输入数据的范围 $[1, 10^3]$；
对于 $70\%$ 的数据，所有输入数据的范围 $[1, 10^5]$；
对于 $100\%$ 的数据，所有输入数据的范围 $[1, 10^6]$；