Squirrel Liss 对序列感兴趣。她也对整数有偏好。她认为n个整数a1,a2,...,an是好的。
现在她对好的序列感兴趣。如果序列 x1, x2, ..., xk 满足以下三个条件,则称为良好序列:
- 序列严格递增,即对于每个 i,xi < xi + 1 (1 ≤ i ≤ k - 1)。
- 没有两个相邻元素互质,即对于每个 i (1 ≤ i ≤ k - 1),gcd(xi, xi + 1) > 1(其中 gcd(p, q) 表示整数 p 和 q 的最大公约数)。
- 序列中的所有元素都是好整数。
找到最长的好序列的长度。
输入
输入由两行组成。第一行包含一个整数 n (1 ≤ n ≤ 105) — 好整数的数量。第二行包含一个以单空格分隔的好整数 a1、a2、...、an 列表,按严格递增顺序 (1 ≤ ai ≤ 105;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
注意
在第一个示例中,以下序列是良好序列的示例:[2; 4; 6; 9],[2; 4; 6],[3; 9],[6]。最长的好序列的长度是4。