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>).
def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)


def f0(arr):
    def dfs(i):
        if i == n:
            nonlocal ans, the
            if ans < len(path):
                ans = len(path)
                the = path[:]
            return
        ai = arr[i]
        dfs(i + 1)
        if len(path) == 0 or (path[-1] < ai and gcd(path[-1], ai) > 1):
            path.append(ai)
            dfs(i + 1)
            path.pop()

    the = None
    ans = 0
    n = len(arr)
    path = []
    dfs(0)
    return ans


def f1(arr):
    pre = {}
    for x in arr:
        maxv = 0
        xx = x
        i = 2
        while i * i <= xx:
            if xx % i == 0:
                maxv = max(maxv, pre.get(i, 0))
                while xx % i == 0:
                    xx //= i
            i += 1
        if xx > 1:
            maxv = max(maxv, pre.get(xx, 0))
        maxv += 1

        xx = x
        i = 2
        while i * i <= xx:
            if xx % i == 0:
                pre[i] = max(pre.get(i, 0), maxv)
                while xx % i == 0:
                    xx //= i
            i += 1
        if xx > 1:
            pre[xx] = max(pre.get(xx, 0), maxv)
    if not pre:
        return 1
    return max(pre.values())


def test():
    from utils.oj import J
    import numpy.random as r
    N = 25
    M = 1000
    T = 10000
    for t in range(T):
        n = r.randint(1, N + 1)
        arr = r.randint(1, M, n).tolist()
        arr = sorted(set(arr))
        J.same(funcs=(f0, f1), arr=arr)
        if t % 100 == 0:
            print(t)
    print("ac")


if __name__ == '__main__':
    def main():
        from utils.oj import J
        J.multi(test)


    # test()
    # main()

_ = input()
arr = list(map(int, input().split()))
print(f1(arr))
