咕咕咕？

Home_W今天在给17级新生讲DP的优化，但是LIWEI咕咕咕了，所以他让Home_W给自己再讲一次，但是Home_W不肯

但是Home_W不想让LIWEI就这么溜了，因为他咕咕咕了，所以他出了一道题给LIWEI

题目如下：给你一个数组a，长度不超过100000，a[i]不超过100000，找出最长不互质子序列

就是gcd(a[i],a[i+1])!=1,a[i]和a[i+1]可以在数组的位置中不连续

Home_W说了，只要LIWEI能接触这道题，他就给LIWEI讲DP的决策优化，但是LIWEI今天状态不好，所以他把题目交给了你们

第一行输入一个数n,n不大于100000

接下来n行，每行输入一个整数x且x不大于100000

输出这个序列的最长不互质序列的长度

3
2
1
6

2