Problem Statement

You are given a sequence $A_0 \dots A_{N - 1}$ of length $N$.
Among its subsequences $ A_{i_0} \dots A_{i_{K - 1}}\ (0 \leq i_0 < \dots < i_{K - 1} < N) $ satisfying both of the following 2 conditions,

• Each term divides the next term: $ A_{i_0} | A_{i_1} | \dots | A_{i_{K - 1}} $
• It is strictly increasing: $A_{i_0} < A_{i_1} < \dots < A_{i_{K - 1}}$

(21:43 Corrected $a_i$ to $A_i$)

Input

$N$
$A_0 \dots A_{N - 1}$

The input consists of 2 lines in total and satisfies the following constraints.

• All input values are integers
• $1 \leq N \leq 3 \times 10 ^ 5$
• $1 \leq A_i \leq 3 \times 10^5\ (0 \leq i < N)$

Output

Print on one line the length of the longest subsequence satisfying the conditions.

Sample

5
2 4 6 1 8

3

5
1 3 3 9 2

3

1
1

1