This problem is about sequences of positive integers $a_1,a_2,...,a_N$. 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 $a_1,a_2,...,a_N$ where $a_i$ divides $a_j$ 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:-----
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 $a_i$.

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

-----Constraints:-----
- $1 \leq N \leq 10000$
- $1 \leq a_i \leq 1000000000$

-----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

Difficulty: interview

Starter code:

Solutions:
# coding: utf-8
# Your code here!

n=int(input())
a=[]
for i in range(n):
    x=int(input())
    a.append(x)
    
# print(a)
ans=0
m=[1]*n
for i in range(n):
    for j in range(i):
        if a[i]%a[j]==0:
            m[i]=max(m[i],m[j]+1)
            
            
            
print(max(m))

#author : dokueki

import sys


def IOE():
    sys.stdin = open("input.txt", "r")
    sys.stdout = open("output.txt", "w")


def dp(a, n):
    mat = [0 for i in range(n)]
    mat[0] = 1
    for i in range(n):
        mat[i] = 1
        for j in range(i):
            if mat[j] != 0 and a[i] % a[j] == 0:
                mat[i] = max(mat[i], mat[j] + 1)
    return max(mat)


def main():
    n = int(sys.stdin.readline())
    a = []
    for _ in range(n):
        a.append(int(sys.stdin.readline()))
    # print(a)
    print(dp(a, n))


def __starting_point():
    try:
        IOE()
    except:
        pass
    main()

__starting_point()

n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
ans = [1] * n
for i in range(n-2, -1, -1):
    for j in range(i+1, n):
        if(a[j] % a[i] == 0):
            ans[i] = max(ans[i], 1 + ans[j])
print(max(ans))

arr=[]
n=int(input())
d=[1]*n
for j in range(n) :
    x=int(input())
    for i in range(len(arr)) :
        if x%arr[i]==0 :
            d[j] = max(d[j] , (d[i]+1))
    arr.append(x)
print(max(d))

# cook your dish here
try:
    x = []
    n = int(input())
    for _ in range(n):
        x.append(int(input()))
    dp = [1]*n
    for i in range(n):
        for j in range(i):
            if x[i] % x[j] == 0:
                dp[i] = max(dp[i],dp[j]+1)
    print(max(dp))
except:
    pass