# The greatest sequence multiple subsequence

Easy

Execution time limit is 1 second

Runtime memory usage limit is 64 megabytes

Given a numeric sequence $a_{1},a_{2},…,a_{n}$, you need to find the length of the longest divisible subsequence.

For a divisible subsequence $a_{k_{1}},a_{k_{2}},…,a_{k_{t}}$ ($k_{1}<k_{2}<⋯<k_{t}$), the condition $a_{k_{i}}∣a_{k_{j}}$ holds true for $1≤i<j≤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≤N≤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

Input #1

Answer #1

Submissions 4K

Acceptance rate 17%