Problem 1: Dividing Sequences, (K Narayan Kumar, CMI)

This problem is about sequences of positive integers a1,a2,...,aN. A subsequence of a sequence is anything obtained by dropping some of the elements. For example, 3,7,11,3 is a subsequence of 6,3,11,5,7,4,3,11,5,3 , but 3,3,7 is not a subsequence of 6,3,11,5,7,4,3,11,5,3 .

A fully dividing sequence is a sequence a1,a2,...,aN where ai divides aj whenever i < j. For example, 3,15,60,720 is a fully dividing sequence.

Given a sequence of integers your aim is to find the length of the longest fully dividing subsequence of this sequence.

Consider the sequence 2,3,7,8,14,39,145,76,320

It has a fully dividing sequence of length 3, namely 2,8,320, but none of length 4 or greater.

Consider the sequence 2,11,16,12,36,60,71,17,29,144,288,129,432,993 .

It has two fully dividing subsequences of length 5,

• 2,11,16,12,36,60,71,17,29,144,288,129,432,993 and
• 2,11,16,12,36,60,71,17,29,144,288,129,432,993

and none of length 6 or greater.

Input format

The first line of input contains a single positive integer N indicating the length of the input sequence. Lines 2,...,N+1 contain one integer each. The integer on line i+1 is ai.

Output format

Your output should consist of a single integer indicating the length of the longest fully dividing subsequence of the input sequence.

Test Data

You may assume that N ≤ 10000.

Example:

Here are the inputs and outputs corresponding to the two examples discussed above.

Sample input 1:

```9
2
3
7
8
14
39
145
76
320
```

Sample output 1:

```3
```

Sample input 2:

```14
2
11
16
12
36
60
71
17
29
144
288
129
432
993
```

Sample output 2:

```5
```

Test data:

 CPU Timelimit: 3 seconds Memory limit: 64M Grading style: ioi
 Username Password Register Now