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>).
# there are at most sqrt(10^5) = 317 prime factors for each number

import sys
from math import sqrt

def prime_factorize(x, primes):
    factorization = []
    for p in primes:
        while x % p == 0:
            factorization.append(p)
            x /= p
    if x > 1:
        factorization.append(x)
    return factorization

ans = 0
primes = {}
prime_table = [True for i in range(100001)]
for i in range(2, 100001):
    if prime_table[i]:
        primes[i] = 0
        j = 2*i
        while j <= 1e5:
            prime_table[j] = False
            j += i

n = int(sys.stdin.readline())
a = [int(x) for x in sys.stdin.readline().split()]

for x in a:
    if x == 1:
        ans = 1
        continue
    # find all prime divisors of x
    divs = prime_factorize(x, primes)
    if len(divs) > 0:
        mx = max([primes[d] for d in divs])
        for d in divs:
            primes[d] = mx+1

ans = max(max([primes[p] for p in primes]), ans)
print(ans)