给定一个长度为 n 的严格单调递增整数序列 a1,a2,…,an，请你找出该序列的一个最长子序列，要求该子序列满足任意两个相邻元素不互质。
输出满足条件的最长子序列的长度。
输入格式
第一行包含整数 n。
第二行包含 n 个整数 a1,a2,…,an。
输出格式
一个整数，表示满足条件的最长子序列的长度。
数据范围
前 66 个测试点满足 1≤n≤10。
所有测试点满足 1≤n≤10^5，1≤ai≤10^5，ai<ai+1。
输入样例1：
5
2 3 4 6 9
输出样例1：
4
输入样例2：
9
1 2 3 5 6 7 8 9 10
输出样例2：
4 