题目描述

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

输入格式

   第一行一个数n，范围[1..1000]；

   第二行n整数，范围[1..1000000]；

输出格式

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

输入/输出例子1

6
9 8 6 7 20 10

4