题目描述

求一个数列中最长互质子序列的长度的问题。

互质子序列要求所有相邻的 2 个数最大公约数为1。例如数列: 1 7 2 8 3 4 ，它的最长互质子数列就是 1 7 2 3 4。

输入格式
第一行一个数n，范围[1,1000]
第二行n整数，范围[1,1000000]

输出格式
一个整数，为最长互质子序列的长度。

样例

6
9 8 6 7 20 10

4