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>).
#include <bits/stdc++.h>

#define ld long double
#define ll long long
#define ull unsigned

#define f first
#define s second
#define endl '\n'
#define pii pair < int, int >

#define ios ios_base::sync_with_stdio(0), cin.tie()
#define pb push_back
#define mp make_pair

#define pi 3.14159265358979323846264
#define y1 abacaba

using namespace std;

const int MXN = 1e6 + 10;
const int MAXN = 1e3 + 1;
const ll INF = 1e9 + 7;
const ll BINF = 1e15;
const int MOD = 1e9 + 9;
const ld EPS = 1e-15;

ll n;
ll mx;
ll a[MXN];
ll dp[MXN], dp1[MXN];

int main(){
    ios;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    } for(int i = 1; i <= n; i++){
        int x = a[i];
        mx = 0;
        for(int j = 2; j * j <= x;){
            if(x % j == 0){
                x /= j;
                mx = max(mx, dp1[j]);
            }
            else j++;
        } if(x > 0) mx = max(mx, dp1[x]);
        dp[i] = mx + 1, x = a[i];
        for(int j = 2; j * j <= x;){
            if(x % j == 0){
                x /= j;
                dp1[j] = max(dp1[j], dp[i]);
            }
            else j++;
        } if(x > 0) dp1[x] = max(dp1[x], dp[i]);
    } mx = 0;
    for(int i = 1; i <= n; i++){
        mx = max(mx, dp[i]);
    } cout << mx;
    return 0;
}
