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>).
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(dp[n-1])