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