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 IO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define S second
#define F first
#define ll long long
#define ld long double
#define u unsigned
#define pi 3.141592653589793238462643383279502884

using namespace std;

ll n, dp[100005];
bool isp[100005];
vector <vector<int>> p(100005);
vector <int> x;

ll solve(int ind, int mod)
{
    if(ind == n)return 0;
    ll ans = solve(ind+1, mod), mx = 0;
    if(x[ind]%mod == 0)
    {
        if(~dp[ind])return max(dp[ind], ans);
        for(int i = 0 ; i < p[x[ind]].size(); i++)
        {
            mx = max(mx, solve(ind+1, p[x[ind]][i])+1);
        }
        dp[ind] = mx;
        return max(dp[ind], ans);
    }
    return ans;
}

int main()
{
    memset(dp, -1, sizeof dp);
    cin>>n;
    x = vector <int> (n+1);
    for(int i = 0 ; i < n ; i++)cin>>x[i];
    for(ll i = 2 ; i < 1e5+1 ; i++)
    {
        if(isp[i])continue;
        p[i].push_back(i);
        for(ll j = i+i; j < 1e5+1 ; j+=i)
        {
            isp[j] = 1;
            p[j].push_back(i);
        }
    }
    cout<<max(solve(0, 1), (ll)1);
    return 0;
}
