Squirrel Liss is interested in sequences. She also has preferences of integers. She thinks *n* integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> are good.

Now she is interested in good sequences. A sequence *x*<sub class="lower-index">1</sub>, *x*<sub class="lower-index">2</sub>, ..., *x*<sub class="lower-index">*k*</sub> is called good if it satisfies the following three conditions:
 -  The sequence is strictly increasing, i.e. *x*<sub class="lower-index">*i*</sub> &lt; *x*<sub class="lower-index">*i* + 1</sub> for each *i* (1 ≤ *i* ≤ *k* - 1). -  No two adjacent elements are coprime, i.e. *gcd*(*x*<sub class="lower-index">*i*</sub>, *x*<sub class="lower-index">*i* + 1</sub>) &gt; 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.
The input consists of two lines. The first line contains a single integer *n* (1 ≤ *n* ≤ 10<sup class="upper-index">5</sup>) — the number of good integers. The second line contains a single-space separated list of good integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> in strictly increasing order (1 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">5</sup>; *a*<sub class="lower-index">*i*</sub> &lt; *a*<sub class="lower-index">*i* + 1</sub>).
import math

def solve():
  n = int(input())
  # l, r = list(map(int, input().split(" ")))
  a = list(map(int, input().split(" ")))
  # b = list(map(int, input().split(" ")))
  # s = input()

  N = int(10e5  + 5)

  dp = [0]*N
  fac = [[] for _ in range(N)]
  seive = [1] * N

  for i in range(2, N):
    if seive[i]:
      for j in range(i, N, i):
        seive[j] = 0
        fac[j].append(i)
  
  ans = 1

  for i in range(n):
    z = 0
    for x in fac[a[i]]:
      z = max(dp[x], z)
    
    z += 1
    ans = max(ans, z)
    
    for x in fac[a[i]]:
      dp[x] = max(z, dp[x])

  print(ans)

  return 


# for _ in range(int(input())):
#   solve()

solve()
