题目描述

给定⼀个正整数序列 $a1$, $a2$, $...$, $an$。 你需要挑出这个序列的⼀个 ⼦序列，使得这个⼦序列的任意两个相邻元素不互质。

输入格式

输入一个$n$ 输入$n$个数字$ai$

样例

样例输入 1

6
2 3 3 3 3 3

样例输出 1

5

数据范围与提示

对于 $30\%$ 的数据，$n$ ≤ $10000$ ，$ai$ ≤ $1000$。

对于 $100\%$ 的数据 $n$ ≤ $100000$，$ai$ ≤ $1000$。