The greatest sequence multiple subsequence

Given a numeric sequence $a_1,a_2,\dots ,a_n$, you need to find the length of the longest divisible subsequence.

For a divisible subsequence $a_{k_1},a_{k_2},\dots ,a_{k_t}$ ($k_1<k_2<\cdots <k_t$), the condition $a_{k_i}|a_{k_j}$ holds true for $1\le i<j\le t$ (the statement $a|b$ means $b$ is divisible by $a$). A subsequence with one element is considered divisible by definition.

Input

The first line of the input file contains a single natural number $N$ ($1\le N\le 1000$) — the number of elements in the given sequence. The next line contains $N$ integers, each of absolute value not exceeding $10^9$, which form the sequence.

Output

Output a single number equal to the desired length.

Examples