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

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
n = int(input())
a = []
for i in range(n):
	x = int(input())
	a.append(x)
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))


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


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