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> // for vector
 
using namespace std;
 

int main()
{
  int n;
  cin>>n;
  int arr[n]={};
  int max1=0;
  for(int i=0;i<n;i++){
    cin>>arr[i];
    max1=max(max1,arr[i]);
  }
  int count[max1+1]={};
  for(int i=2;i<=max1;i++){
    count[i]=i;
  }
  for(int i=2;i<=max1;i++){
    if(count[i]==i){
      for(long long int j=i*i;j<=max1;j=j+i){
      if(count[j]==j){
        count[j]=i;
      }
     }
    }
     
  }
  map<int,int>m1;
  int ans=1;
  for(int i=0;i<n;i++){
    int n1=arr[i];
    int n2=arr[i];
    int prev=1;
    int ans1=1;
    while(n1>1){
      int fact=count[n1];
      if(prev!=fact){
        m1[fact]++;
        ans1=max(ans1,m1[fact]);
      }
    
      n1=n1/fact;
      prev=fact;
    }
    while(n2>1){
      int fact=count[n2];
      m1[fact]=ans1;
    
      n2=n2/fact;
    }
    ans=max(ans,ans1);

  }  
  cout<<ans<<endl;

  
 
  return 0;

  
}