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 append push_back
#define add insert
#define print(x) cout<<x<<" "<<endl;
#define setbit(a,i) (1>>i)&a
using namespace std;
template<class T>
ostream& operator<<(ostream& os, vector<T> v) {
    cout << "[";
    for(auto &i: v) cout << i << ", ";
    cout << "]" << endl;
    return os;
}
template<class T>
ostream& operator<<(ostream& os, set<T> v) {
    cout << "[";
    for(auto &i: v) cout << i << ", ";
    cout << "]" << endl;
    return os;
}

template <typename K, typename V>
ostream& operator<<(ostream& os, pair<K, V> p) {
    os << "{" << p.first << ", " << p.second << "} ";
    return os;
}
const int N=1e5+5;
vector<int> dp(N,0),d(N,0);
vector<int> div(int x) 
{
    vector<int> tem;
    tem.push_back(x);
    for (int i = 2; i * i <= x;i++) 
    {
        if(x%i==0)
        {
      	  	tem.push_back(i);
        	tem.push_back(x/i);
        }
    }
    return tem;
}
int32_t main()
{
	ios::sync_with_stdio(NULL);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	vector<int>ar(n);
	for(int i=0;i<n;i++)
		cin>>ar[i];
 	for(auto i:ar)
 	{
 		vector<int>temp=div(i);
 		for(auto j:temp)
 		{
 			dp[i]=max(dp[i],d[j]+1);
 		}
 		for(auto j:temp)
 		{
 			d[j]=max(d[j],dp[i]);
 		}
 	}
	cout<<*max_element(dp.begin(),dp.end());
}
