当前没有测试数据。

题目描述

小A给出了n个好的数字，现在希望小A能从中选出一些数严格递增的排在一起，使得任意相邻两个数的gcd都大于1。

小A希望知道这样选出的数最多有多少个。

输入格式

输入第一行一个数N表示可以使用的位数。

第二行N个数表示好的元素是哪些。

输出格式

输出一行一个整数表示最多能选出的数的数量。

输入输出样例 #1

输入 #1

9
1 2 3 5 6 7 8 9 10

输出 #1

4

说明/提示

对于 $40\%$ 的数据，$n \le 300$；
对于 $80\%$ 的数据，$n \le 5000$；
对于 $100\%$ 的数据，$n$, $ai \le 100000$。