Squirrel Liss is interested in sequences. She also has preferences of integers. She thinks n integers a_1, a_2, ..., a_{n} are good.

Now she is interested in good sequences. A sequence x_1, x_2, ..., x_{k} is called good if it satisfies the following three conditions:  The sequence is strictly increasing, i.e. x_{i} < x_{i} + 1 for each i (1 ≤ i ≤ k - 1).  No two adjacent elements are coprime, i.e. gcd(x_{i}, x_{i} + 1) > 1 for each i (1 ≤ i ≤ k - 1) (where gcd(p, q) denotes the greatest common divisor of the integers p and q).  All elements of the sequence are good integers. 

Find the length of the longest good sequence.


-----Input-----

The input consists of two lines. The first line contains a single integer n (1 ≤ n ≤ 10^5) — the number of good integers. The second line contains a single-space separated list of good integers a_1, a_2, ..., a_{n} in strictly increasing order (1 ≤ a_{i} ≤ 10^5; a_{i} < a_{i} + 1).


-----Output-----

Print a single integer — the length of the longest good sequence.


-----Examples-----
Input
5
2 3 4 6 9

Output
4

Input
9
1 2 3 5 6 7 8 9 10

Output
4



-----Note-----

In the first example, the following sequences are examples of good sequences: [2; 4; 6; 9], [2; 4; 6], [3; 9], [6]. The length of the longest good sequence is 4.

Source: codeforces | Difficulty: MEDIUM
Tags: Number theory

Dynamic programming


Solutions:
def main():
	input()
	d = {}
	for a in map(int, input().split()):
		(z, l) = (0, [])
		for p in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313):
			if not a % p:
				l.append(p)
				x = d.get(p, 0)
				if z < x:
					z = x
				a //= p
				while not a % p:
					a //= p
				if a == 1:
					break
		else:
			l.append(a)
			x = d.get(a, 0)
			if z < x:
				z = x
		d.update(dict.fromkeys(l, z + 1))
	print(max(d.values()))
main()


import math
N = 100100

def solve(ar):
	n = len(ar)
	dp = [0 for i in range(N + 20)]
	for a in ar:
		x = math.sqrt(a)
		dp[a] = 1
		for j in range(2, a):
			if j * j <= a:
				if a % j == 0:
					dp[a] = max(dp[a], max(dp[a // j] + 1, dp[j] + 1))
			else:
				break
		for j in range(2, a):
			if j * j <= a:
				if a % j == 0:
					dp[j] = dp[a // j] = dp[a]
			else:
				break
	m = 1
	for x in range(1, 100100):
		m = max(m, dp[x])
	return m
n = int(input())
ar = list(map(int, input().split()))
x = solve(ar)
print(x)


n = 100001
p = [0] * n
y = [[] for i in range(n)]
y[1] = [1]
for i in range(2, n):
	if not y[i]:
		y[i] = [i]
		for j in range(2 * i, n, i):
			y[j].append(i)

def prob():
	n = int(input())
	l = [int(x) for x in input().split()]
	for i in l:
		k = max((p[j] for j in y[i])) + 1
		for j in y[i]:
			p[j] = k
	print(max(p))
t = 1
for _ in range(0, t):
	prob()


n = 100001
p = [0] * n
t = [[] for i in range(n)]
t[1] = [1]
for i in range(2, n):
	if not t[i]:
		t[i] = [i]
		for j in range(2 * i, n, i):
			t[j].append(i)
input()
a = list(map(int, input().split()))
for i in a:
	x = max((p[j] for j in t[i])) + 1
	for j in t[i]:
		p[j] = x
print(max(p))


n = int(input())
a = list(map(int, input().split()))
dp = [1] * (n + 5)
tmax = [0 for _ in range(100005)]
p = [[] for _ in range(100005)]
p[1] = [1]
for i in range(2, 100001):
	if p[i] == []:
		for j in range(i, 100001, i):
			p[j].append(i)
for i in range(len(a)):
	dp[i] = max((tmax[j] for j in p[a[i]])) + 1
	for j in p[a[i]]:
		tmax[j] = max(tmax[j], dp[i])
print(max(dp))


from sys import stdin
mem = [0 for i in range(int(100000.0 + 1))]

def solve(tc):
	n = int(stdin.readline().strip())
	seq = list(map(int, stdin.readline().split()))
	if n == 1:
		print(1)
		return
	ans = 0
	for i in range(n):
		num = seq[i]
		divisor = set()
		p = 2
		while p * p <= num:
			while num % p == 0:
				divisor.add(p)
				num //= p
			p += 1
		if num > 1:
			divisor.add(num)
		for dn in divisor:
			mem[seq[i]] = max(mem[seq[i]], mem[dn] + 1)
		for dn in divisor:
			mem[dn] = mem[seq[i]]
		ans = max(ans, mem[seq[i]])
	print(ans)
tcs = 1
for tc in range(tcs):
	solve(tc)


from collections import defaultdict
import math

def primeFactors(n):
	prime = set()
	while n % 2 == 0:
		prime.add(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			prime.add(i)
			n = n // i
	if n > 2:
		prime.add(n)
	return list(prime)
n = int(input())
a = list(map(int, input().split()))
l = defaultdict(int)
for i in range(n):
	pf = primeFactors(a[i])
	mx = 0
	for j in pf:
		mx = max(mx, l[j])
	for j in pf:
		l[j] = mx + 1
mx = 1
for (k, v) in l.items():
	mx = max(mx, v)
print(mx)


p = 10 ** 5 + 9
t = [[] for i in range(p)]
dp = [0] * p
for i in range(2, p):
	if not t[i]:
		t[i].append(i)
	for j in range(2 * i, p, i):
		t[j].append(i)
n = int(input())
l = [int(i) for i in input().split()]
if n == 1:
	print(1)
	return
for i in l:
	maxi = 0
	for j in t[i]:
		maxi = max(maxi, dp[j])
	dp[i] = maxi + 1
	for j in t[i]:
		dp[j] = maxi + 1
print(max(dp))


import math
primes = []

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
	for p in range(n + 1):
		if prime[p]:
			primes.append(p)
SieveOfEratosthenes(6000)
dp = [0 for i in range(max(primes) + 1)]
n = int(input())
arr = list(map(int, input().strip().split()))
try:
	for i in arr:
		p = []
		for j in primes:
			if j > i:
				break
			if i % j == 0:
				p.append(j)
		maxi = 0
		for j in p:
			maxi = max(dp[j] + 1, maxi)
		for j in p:
			dp[j] = maxi
	print(max(max(dp), 1))
except Exception as e:
	print(e)


lis = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, 5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, 5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473, 6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833, 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, 7507, 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561, 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919, 7927, 7933, 7937, 7949, 7951, 7963, 7993, 8009, 8011, 8017, 8039, 8053, 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111, 8117, 8123, 8147, 8161, 8167, 8171, 8179, 8191, 8209, 8219, 8221, 8231, 8233, 8237, 8243, 8263, 8269, 8273, 8287, 8291, 8293, 8297, 8311, 8317, 8329, 8353, 8363, 8369, 8377, 8387, 8389, 8419, 8423, 8429, 8431, 8443, 8447, 8461, 8467, 8501, 8513, 8521, 8527, 8537, 8539, 8543, 8563, 8573, 8581, 8597, 8599, 8609, 8623, 8627, 8629, 8641, 8647, 8663, 8669, 8677, 8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737, 8741, 8747, 8753, 8761, 8779, 8783, 8803, 8807, 8819, 8821, 8831, 8837, 8839, 8849, 8861, 8863, 8867, 8887, 8893, 8923, 8929, 8933, 8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007, 9011, 9013, 9029, 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109, 9127, 9133, 9137, 9151, 9157, 9161, 9173, 9181, 9187, 9199, 9203, 9209, 9221, 9227, 9239, 9241, 9257, 9277, 9281, 9283, 9293, 9311, 9319, 9323, 9337, 9341, 9343, 9349, 9371, 9377, 9391, 9397, 9403, 9413, 9419, 9421, 9431, 9433, 9437, 9439, 9461, 9463, 9467, 9473, 9479, 9491, 9497, 9511, 9521, 9533, 9539, 9547, 9551, 9587, 9601, 9613, 9619, 9623, 9629, 9631, 9643, 9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721, 9733, 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811, 9817, 9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887, 9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973]
n = int(input())
li = list(map(int, input().split()))
has = [0] * 100005
for i in li:
	mx = 0
	tmp = []
	for j in lis:
		if i < j:
			break
		if i % j == 0:
			mx = max(mx, has[j] + 1)
			tmp.append(j)
	for j in tmp:
		has[j] = mx
print(max(has + [1]))


import sys
input = sys.stdin.buffer.readline
import math

def solution():
	n = int(input())
	l = list(map(int, input().split()))
	dp = [0] * 100005
	cnt = [0] * 100005
	ans = 0
	for i in range(n):
		x = l[i]
		for j in range(1, int(x ** 0.5) + 1):
			if x % j == 0:
				cnt[i + 1] = max(cnt[i + 1], cnt[dp[x // j]] + 1)
				if j > 1:
					cnt[i + 1] = max(cnt[i + 1], cnt[dp[j]] + 1)
				ans = max(ans, cnt[i + 1])
				dp[j] = i + 1
				dp[x // j] = i + 1
	print(ans)
solution()


import math
a = int(input())
z = list(map(int, input().split()))
dp = [0 for i in range(max(z) + 1)]
dp[0] = 1

def fact(x):
	ans = []
	for i in range(2, int(math.sqrt(x)) + 1):
		if x % i == 0:
			if x // i != i:
				ans.append(i)
				ans.append(x // i)
			else:
				ans.append(i)
	ans.append(x)
	return ans
for i in range(len(z)):
	t = fact(z[i])
	maxa = 0
	for i in range(len(t)):
		maxa = max(maxa, dp[t[i]])
	for i in range(len(t)):
		dp[t[i]] = maxa + 1
print(max(dp))


R = lambda : map(int, input().split())
(prime, cnt) = ([1] * 10001, [0] * 10001)
pms = []
for i in range(2, 10001):
	if prime[i]:
		for j in range(i + i, 10001, i):
			prime[j] = 0
		pms.append(i)
n = int(input())
for x in R():
	mx = 0
	coms = []
	for p in pms:
		if x < p:
			break
		if x % p == 0:
			mx = max(mx, cnt[p] + 1)
			coms.append(p)
	for x in coms:
		cnt[x] = mx
print(max(cnt + [1]))


n = 100001
m = int(input())
div = [[] for _ in range(n)]
div[1] = [1]
for i in range(2, n):
	if not div[i]:
		div[i] = [i]
		for j in range(2 * i, n, i):
			div[j].append(i)
a = list(map(int, input().rstrip().split()))
dp = [0] * (n + 1)
for i in a:
	x = max((dp[j] for j in div[i])) + 1
	for j in div[i]:
		dp[j] = x
print(max(dp))


n = int(input())
x = list(map(int, input().split()))
v = [[] for i in range(100001)]
(max, ans) = ([0] * 100001, 0)
for i2 in range(1, x[n - 1] + 1):
	for i in range(i2, x[n - 1] + 1, i2):
		v[i].append(i2)
for i in range(n):
	temp = 0
	for i2 in range(1, len(v[x[i]])):
		if temp < max[v[x[i]][i2]]:
			temp = max[v[x[i]][i2]]
	temp += 1
	for i2 in range(1, len(v[x[i]])):
		if temp > max[v[x[i]][i2]]:
			max[v[x[i]][i2]] = temp
	if ans < temp:
		ans = temp
print(ans)


import bisect
import sys
import math as mt
import collections
import heapq
t = 1
p = 10 ** 9 + 7

def ncr_util():
	inv[0] = inv[1] = 1
	fact[0] = fact[1] = 1
	for i in range(2, 300001):
		inv[i] = inv[i % p] * (p - p // i) % p
	for i in range(1, 300001):
		inv[i] = inv[i - 1] * inv[i] % p
		fact[i] = fact[i - 1] * i % p

def solve():
	dp = [0] * (n + 1)
	if n == 1:
		return 1
	d = {}
	for i in range(n):
		j = 1
		(x, ind) = (0, -1)
		while j * j <= l[i]:
			if l[i] % j == 0:
				if l[i] // j == j and j != 1:
					if d.get(j, -1) != -1:
						x = max(x, d[j])
				else:
					if d.get(j, -1) != -1 and j != 1:
						x = max(x, d[j])
					if d.get(l[i] // j, -1) != -1 and l[i] // j != 1:
						x = max(x, d[l[i] // j])
			j += 1
		j = 1
		while j * j <= l[i]:
			if l[i] % j == 0:
				if l[i] // j == j and j != 1:
					d[j] = max(d.get(j, 0), x + 1)
				else:
					if j != 1:
						d[j] = max(d.get(j, 0), x + 1)
					if l[i] // j != 1:
						d[l[i] // j] = max(d.get(l[i] // j, 0), x + 1)
			j += 1
	maxi = 0
	for i in d:
		maxi = max(maxi, d[i])
	return maxi
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	print(solve())


n = int(input())
a = list(map(int, input().split(' ')))
if a == [1] * n:
	print(1)
else:
	primes = [True for i in range(401)]
	primes[0] = False
	primes[1] = False
	for k in range(1, 401):
		if primes[k] == True:
			for pro in range(k * k, 401, k):
				primes[pro] = False
		mine = []
	for k in range(401):
		if primes[k]:
			mine.append(k)
	d = [0 for i in range(100001)]
	dp = [0 for i in range(n)]
	for k in range(n):
		al = a[k]
		for prime in mine:
			if al % prime == 0:
				dp[k] = max(d[prime] + 1, dp[k])
			while al % prime == 0:
				al //= prime
		for prime in mine:
			if a[k] % prime == 0:
				d[prime] = max(d[prime], dp[k])
		if al != 1:
			dp[k] = max(d[al] + 1, dp[k])
			d[al] = dp[k]
	print(max(dp))


from math import gcd
from math import ceil, sqrt
from collections import defaultdict

def largestPrime(N):
	largerPrime = list(range(N + 1))
	for i in range(2, N + 1):
		if largerPrime[i] == i:
			for j in range(i * 2, N + 1, i):
				largerPrime[j] = i
	return largerPrime
PrimeFactors = defaultdict(list)

def primeFactors(N):
	Large = largestPrime(N)
	for i in range(2, N + 1):
		temp = i
		while i != 1:
			fact = Large[int(i)]
			PrimeFactors[temp].append(Large[int(i)])
			while i % fact == 0:
				i /= fact
N = int(input())
List = [int(x) for x in input().split()]
primeFactors(max(List) + 1)
d = defaultdict(int)
for i in PrimeFactors[List[0]]:
	d[i] = 1
dp = [1] * (N + 1)
for i in range(1, N):
	for j in PrimeFactors[List[i]]:
		if d[j] != 0:
			dp[i] = max(dp[i], dp[d[j] - 1] + 1)
		d[j] = i + 1
print(max(dp))


from sys import stdin
input = lambda : stdin.readline().strip()
from math import ceil, sqrt, factorial, gcd
from collections import deque
from bisect import bisect_right
ma = int(100000.0) + 1
dp = [[] for i in range(ma)]
for i in range(2, ma):
	dp[i].append(i)
	for j in range(i + i, ma, i):
		dp[j].append(i)
dp[1].append(1)
n = int(input())
l = list(map(int, input().split()))
z = [0 for i in range(ma)]
for i in l:
	x = 0
	for j in dp[i]:
		x = max(x, z[j])
	for j in dp[i]:
		z[j] = x + 1
print(max(z))


import bisect
import collections
import copy
import functools
import heapq
import itertools
import math
import random
import re
import string
import sys
import time
from typing import Counter, List
sys.setrecursionlimit(99999)
input()
mx = 10 ** 5 + 5
f = [0] * mx
f[1] = 1
for i in range(2, mx):
	if f[i] == 0:
		f[i] = i
		for j in range(i * i, mx, i):
			if f[j] == 0:
				f[j] = i
mp = collections.defaultdict(int)
for c in map(int, input().split()):
	p = []
	while f[c] != c:
		k = f[c]
		p.append(k)
		while c % k == 0:
			c //= k
	if c > 1:
		p.append(c)
	if p:
		mx = max((mp[x] for x in p))
		for c in p:
			mp[c] = mx + 1
if mp:
	print(max(mp.values()))
else:
	print(1)


n = int(input())
a = [int(i) for i in input().split()]
m = max(a)
sieve = [i for i in range(m + 1)]
for i in range(2, m + 1):
	if sieve[i] == i:
		for j in range(i + i, m + 1, i):
			sieve[j] = i

def prime_factors(x):
	fs = set()
	while x > 1:
		f = sieve[x]
		x //= f
		fs.add(f)
	return fs
prev = {}
dp = [1 for _ in range(n)]
for i in range(n):
	fs = prime_factors(a[i])
	for f in fs:
		j = prev.get(f)
		if j is not None:
			dp[i] = max(dp[i], dp[j] + 1)
	for f in fs:
		prev[f] = i
print(max(dp))


n = 100001
(p, t) = ([0] * n, [[] for i in range(n)])
t[1] = [1]
for i in range(2, n):
	t[i].append(i)
	for j in range(2 * i, n, i):
		t[j].append(i)
n = input()
for i in map(int, input().split(' ')):
	x = max((p[j] for j in t[i])) + 1
	for j in t[i]:
		p[j] = x
print(max(p))


n = 10 ** 5 + 1
p = [0] * n
t = [[] for _ in range(n)]
t[1] = [1]
for i in range(2, n):
	if not t[i]:
		t[i] = [i]
		for j in range(2 * i, n, i):
			t[j].append(i)
m = input()
arr = list(map(int, input().split()))
x = 0
for i in arr:
	x = 0
	for j in t[i]:
		x = max(p[j], x)
	x += 1
	for j in t[i]:
		p[j] = x
print(max(p))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import Counter
import heapq
n = int(input())
arr = list(map(int, input().split()))
dp = [0 for i in range(arr[-1] + 1)]
for i in arr:
	divisors = set()
	for d in range(2, int(i ** 0.5) + 1):
		if i % d == 0:
			divisors.add(d)
			divisors.add(i // d)
	divisors.add(i)
	if divisors:
		dp[i] = max((dp[k] for k in divisors)) + 1
		for j in divisors:
			dp[j] = dp[i]
if n == 1:
	print(1)
else:
	print(max(dp))


ovmaxx = 0
t = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397]
x = int(input())
y = list(map(int, input().split(' ')))
good = [False] * (10 ** 5 + 5)
for i in y:
	good[i] = True
dp2 = [0] * (10 ** 5 + 5)
for i in range(10 ** 5 + 5):
	if not good[i]:
		continue
	pdiv = []
	for a in t:
		k = 0
		while i % a == 0:
			if k == 0:
				pdiv.append(a)
			i //= a
			k = 1
	maxx = 0
	if i != 1:
		pdiv.append(i)
	for i2 in pdiv:
		maxx = max(dp2[i2] + 1, maxx)
	for i2 in pdiv:
		dp2[i2] = max(dp2[i2] + 1, maxx)
	ovmaxx = max(ovmaxx, maxx)
print(max(ovmaxx, 1))


from math import floor, sqrt

def div(x):
	primos = [1 for i in range(x + 1)]
	p = 2
	while p < x + 1:
		if primos[p] == 1:
			for i in range(p * p, x + 1, p):
				if primos[i] == 1:
					primos[i] = p
			primos[p] = p
		p += 1
	return primos

def fat(mindiv, x):
	fat = []
	while x != 1:
		fat.append(mindiv[x])
		x //= mindiv[x]
	return set(fat)

def main():
	n = int(input())
	if n == 1:
		print(1)
		return
	arr = input().split()
	arr = [int(x) for x in arr]
	mindiv = div(arr[-1])
	seq = [0 for i in range(arr[-1] + 1)]
	for num in arr:
		fatores = fat(mindiv, num)
		tam = 0
		for f in fatores:
			tam = max(tam, seq[f])
		for f in fatores:
			seq[f] = tam + 1
	print(max(seq))
	return
main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import factorial
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)
mod = 998244353
INF = float('inf')
from math import sqrt, ceil

def df(num):
	up = ceil(sqrt(num))
	res = set()
	res.add(num)
	for i in range(2, min(up + 1, num)):
		if num % i == 0:
			res.add(i)
			res.add(num // i)
	return list(res)

def main():
	n = N()
	arr = RLL()
	dfarr = [df(i) for i in arr]
	dp = [0] * 111111
	dp[0] = 1
	ma = 0
	for i in range(n):
		now = 0
		for j in range(len(dfarr[i])):
			now = max(now, dp[dfarr[i][j]])
		for j in range(len(dfarr[i])):
			dp[dfarr[i][j]] = now + 1
			ma = max(ma, dfarr[i][j])
	print(max(dp[:ma]))
main()


primes = []
for i in range(2, 10 ** 5):
	x = 0
	for j in range(2, int(i ** 0.5) + 1):
		if i % j == 0:
			x = 1
			break
	if x == 0:
		primes.append(i)
set_p = set(primes)
n = int(input())
a = list(map(int, input().split()))
a = a[::-1]
ans = 0
store = {}
c = 0
for i in a:
	c = 0
	b = set()
	if i == 1:
		ans = max(ans, 1)
	x = i
	for i in primes:
		if x == 1:
			break
		if x in set_p:
			b.add(x)
			break
		if x % i == 0:
			b.add(i)
			while x % i == 0:
				x = x // i
	for i in b:
		if i in store:
			c = max(c, store[i] + 1)
		else:
			c = max(c, 1)
	for i in b:
		store[i] = c
	if c > ans:
		ans = c
print(ans)


from collections import Counter, OrderedDict
from itertools import permutations as perm
from fractions import Fraction
from collections import deque
from sys import stdin
from bisect import *
from heapq import *
from math import *
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
mod = int(1000000000.0) + 7
inf = float('inf')
(n,) = gil()
a = gil()

def getPrimes(x):
	p = []
	if x & 1 == 0:
		p.append(2)
	while x & 1 == 0:
		x //= 2
	for i in range(3, ceil(sqrt(x)) + 1):
		if x % i == 0:
			p.append(i)
		while x % i == 0:
			x //= i
	if x > 1:
		p.append(x)
	return p
primes = {}
ans = 1
for v in a:
	maxP = 0
	local_primes = getPrimes(v)
	for p in local_primes:
		maxP = max(maxP, primes.get(p, 0))
	for p in local_primes:
		primes[p] = maxP + 1
	ans = max(maxP + 1, ans)
print(ans)


import sys, os
from io import BytesIO, IOBase
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque
from heapq import merge, heapify, heappop, heappush, nsmallest
from bisect import bisect_left as bl, bisect_right as br, bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(stdin, stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
mod = pow(10, 9) + 7
mod2 = 998244353

def inp():
	return stdin.readline().strip()

def iinp():
	return int(inp())

def out(var, end='\n'):
	stdout.write(str(var) + '\n')

def outa(*var, end='\n'):
	stdout.write(' '.join(map(str, var)) + end)

def lmp():
	return list(mp())

def mp():
	return map(int, inp().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(m, val) for j in range(n)]

def ceil(a, b):
	return (a + b - 1) // b
S1 = 'abcdefghijklmnopqrstuvwxyz'
S2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

def isprime(x):
	if x <= 1:
		return False
	if x in (2, 3):
		return True
	if x % 2 == 0:
		return False
	for i in range(3, int(sqrt(x)) + 1, 2):
		if x % i == 0:
			return False
	return True

def divs(n):
	ansl = []
	if n % 2 == 0:
		ansl.append(2)
		while n % 2 == 0:
			n //= 2
	j = 3
	while j * j <= n:
		if n % j == 0:
			ansl.append(j)
			while n % j == 0:
				n //= j
		j += 2
	if n > 1:
		ansl.append(n)
	return ansl
n = iinp()
arr = lmp()
dp = l1d(n)
f = dd(int)
for i in range(n):
	divisors = divs(arr[i])
	for x in divisors:
		dp[i] = max(dp[i], 1 + f[x])
	for x in divisors:
		f[x] = dp[i]
print(max(1, max(dp)))


import math
n = int(input())
l = list(map(int, input().split()))[:n]
dp = [0 for j in range(max(l) + 1)]
for x in l:
	divi = set()
	for k in range(2, int(math.sqrt(x)) + 1):
		if not x % k:
			divi.add(x // k)
			divi.add(k)
	divi.add(x)
	if divi:
		dp[x] = max([dp[k] for k in divi]) + 1
		for d in divi:
			dp[d] = dp[x]
if len(l) == 1:
	print(1)
else:
	print(max(dp))


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict as dd, deque as dq
import math, string

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())
MOD = 10 ** 9 + 7

def prime_factors(n):
	factors = []
	num = 0
	while n % 2 == 0:
		num += 1
		n //= 2
	if num:
		factors.append(2)
	i = 3
	while n > 1 and i * i <= n:
		num = 0
		while n % i == 0:
			num += 1
			n //= i
		if num:
			factors.append(i)
		i += 2
	if n > 2:
		factors.append(n)
	return factors

def solve():
	N = getInt()
	A = [0] + getInts()
	prime_last_index = dd(int)
	dp = [1] * (N + 1)
	for i in range(1, N + 1):
		facs = prime_factors(A[i])
		for fac in facs:
			last = prime_last_index[fac]
			if last:
				dp[i] = max(dp[last] + 1, dp[i])
			prime_last_index[fac] = i
	return max(dp)
print(solve())


n = int(input())
inf = 200001
p = [0] * inf
a = [[] for _ in range(inf)]
a[1] = [1]
for i in range(2, inf):
	a[i].append(i)
	for j in range(i * 2, inf, i):
		a[j].append(i)
for i in map(int, input().split()):
	mx = max((p[j] for j in a[i])) + 1
	for j in a[i]:
		p[j] = mx
print(max(p))