题目描述

小明在家打游戏，楼下在跳广场舞，吵死了。

有$n$个舞者排成一排，第$i$个舞者的属性是$a_i$。

在每一刻，一个人可以邀请自己左侧或者右侧相邻的人跳舞，如果这两个人的属性的最大公约数$>1$，则这个人很开心，然后会开心回家睡觉。此时，他离开了跳舞的队列，他左右侧的两个人现在相邻了。

广场舞可太吵了，问：假设小明可以安排跳舞的顺序，最多能让多少个人回家睡觉！

输入格式

第一行输入$n$。

接下来一行输入$n$个正整数表示$a_i$。

输出格式

一个数字表示答案。

样例输入 #1

5
1 6 3 2 4

样例输出 #1

3

样例解释 #1

让$3$先跟$2$跳舞，跳完走人。让$4$跟$2$跳舞，跳完走人。让$5$跟$2$跳舞，跳完走人。

剩下俩人，分别属性是$1,6$，他俩去广场上站着吧。

样例输入 #2

6
6 2 3 4 15 9

样例输出 #2

5

数据范围

对于30%的数据：$n\leq 20$。

对于70%的数据：$n\leq 100$。

对于100%的数据：$n\leq 500,1\leq a_i\leq 10^9$。