Reference: Codeforces 264B — Good Sequences

You are given ~n~ distinct positive integers:

~a_1, a_2, \ldots, a_n~

in strictly increasing order.

A sequence ~x_1, x_2, \ldots, x_k~ is called good when all the following conditions hold:

• Every element of the sequence belongs to the given set of integers.
• The sequence is strictly increasing.
• Every two adjacent elements have a greatest common divisor greater than ~1~.

Formally:

~gcd(x_i, x_{i+1}) > 1~

for every ~1 \le i < k~.

Find the maximum possible length of a good sequence.

Input

• The first line contains one integer ~n~.
• The second line contains ~n~ integers in strictly increasing order: ~a_1, a_2, \ldots, a_n~.

Output

• Print one integer: the maximum length of a good sequence.

Constraints

• ~1 \le n \le 10^5~
• ~1 \le a_i \le 10^5~
• ~a_i < a_{i+1}~

Example 1

Input:

5
2 3 4 6 9

Output:

4