/**************Powered by Graphene Richards**************/
//{

#define FLOAT_PRECISION     2

#ifdef _MSC_VER
#define _SECURE_SCL 0
#pragma comment(linker,"/STACK:102400000,102400000")
#else
#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
#endif
#if defined(_MSC_VER)||__cplusplus>199711L
#define IT(x) auto
#define DIT(x) auto
#else
#define IT(x) __typeof((x).begin())
#define DIT(x) __typeof((x).rbegin())
#endif

#  inc\
lude<cmath>
#  inc\
lude<cstdio>
#  inc\
lude<cstdlib>
#  inc\
lude<cstring>
#  inc\
lude<algorithm>
#  inc\
lude<bitset>
#  inc\
lude<complex>
#  inc\
lude<vector>
#  inc\
lude<iomanip>
#  inc\
lude<iostream>
#  inc\
lude<list>
#  inc\
lude<map>
#  inc\
lude<queue>
#  inc\
lude<set>
#  inc\
lude<stack>
#  inc\
lude<string>
#define FAST_RW ios_base::sync_with_stdio(0),cin.tie(0);
#define FS(i,a) for(ll i=0;a[i];i++)
#define FE(x,ctn) for(IT(ctn) x=(ctn).begin(),_en=(ctn).end();x!=_en;x++)
#define EF(x,ctn) for(DIT(ctn) x=(ctn).rbegin(),_en=(ctn).rend();x!=_en;x++)
#define FR(i,en) for(ll i=0,_en=(en);i<_en;i++)
#define FOR(i,en) for(ll i=1,_en=(en);i<=_en;i++)
#define RF(i,en) for(ll i=(en)-1;i>=0;i--)
#define ROF(i,en) for(ll i=(en);i>0;i--)
#define FFR(i,x,y) for(ll i=(x),_en=(y);i<=_en;i++)
#define RFF(i,x,y) for(ll i=(x),_en=(y);i>=_en;i--)
#define pc putchar
#define pb push_back
#define ppb pop_back
#define pq priority_queue
#define fi first
#define se second
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sqr(x) ((x)*(x))
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define clr(x) memset((x),0,sizeof(x))
#define ms(x,v) memset((x),(v),sizeof(x))
#define mc(x,y) memcpy((x),(y),sizeof(y))
#define NL puts("");
#define LB lower_bound
#define UB upper_bound
#define rand() ((rand()<<16)^(rand()<<15)^(rand()))
#ifdef _WIN32
#define _i64_ "%I\
64d"
#define _u64_ "%I\
64u"
#else
#define _i64_ "%l\
ld"
#define _u64_ "%l\
lu"
#endif
typedef unsigned ui;
typedef long long ll;
typedef unsigned long long ull;
typedef long double lf;
using namespace std;

ull gcd(ull a,ull b){if(!b)return a;while(b^=a^=b^=a%=b);return a;}

extern const ll MOD;
ll ksm(ll a,ll b){
  ll res=1;
  a%=MOD;
  for(;b;b>>=1){
    if(b&1)res=res*a%MOD;
    a=a*a%MOD;
  }
  return res;
}

#ifdef wmx16835
#include"wmx16835.h"
#else
#define LOG
#define TEL
#define test(...) 0
#define TEST(...) 0
#define TRY(...)
#define SF(...)
#define SC
#define PF
#define PC
#define PP
#define SHOW_TIME
#define BR
#endif

template<class T1,class T2,class T3>bool In(T1 x,T2 y,T3 z){return x<=y&&x>=z||x<=z&&x>=y;}
template<class T1,class T2>T1 max(const T1&a,const T2&b){return a<b?b:a;}
template<class T1,class T2,class T3>T1 max3(const T1&a,const T2&b,const T3&c){return a<b?(b<c?c:b):(a<c?c:a);}
template<class T1,class T2>T1 min(const T1&a,const T2&b){return a<b?a:b;}
template<class T1,class T2,class T3>T1 min3(const T1&a,const T2&b,const T3&c){return a<b?(a<c?a:c):(b<c?b:c);}

bool S(char*a){return scanf("%s",a)==1;}
bool S(int&a){return scanf("%d",&a)==1;}
bool S(bool&a){return scanf("%d",&a)==1;}
bool S(ui&a){return scanf("%u",&a)==1;}
bool S(float&a){return scanf("%f",&a)==1;}
bool S(double&a){return scanf("%lf",&a)==1;}
bool S(ll&a){return scanf(_i64_,&a)==1;}
bool S(ull&a){return scanf(_u64_,&a)==1;}
bool S(lf&a){double b;if(scanf("%lf",&b)==-1)return 0;a=b;return 1;}
bool S(char&a){char b[2];if(scanf("%1s",b)==-1)return 0;a=*b;return 1;}
bool SL(char*a){a[0]=0;while(gets(a)&&!a[0]);return a[0];}
template<class T1,class T2>bool S(pair<T1,T2>&a){S(a.fi),S(a.se);}
template<class T>bool S(T&a){a.in();}

void _P(const int&x){printf("%d",x);}
void _P(const bool&x){printf("%d",x);}
void _P(const ui&x){printf("%u",x);}
void _P(const char&x){printf("%c",x);}
void _P(const char*x){printf("%s",x);}
void _P(const string&x){printf("%s",x.c_str());}
void _P(const ll&x){printf(_i64_,x);}
void _P(const ull&x){printf(_u64_,x);}
void _P(const float&x){printf("%.*f",FLOAT_PRECISION,x);}
void _P(const double&x){printf("%.*f",FLOAT_PRECISION,x);}
void _P(const lf&x){printf("%.*f",FLOAT_PRECISION,(double)x);}
template<class T1,class T2>void _P(const pair<T1,T2>&x){_P(x.fi);pc(' ');_P(x.se);}
template<class T>void _P(const T&a){a.out();}

template<class T1,class T2>bool S(T1&a,T2&b){return S(a)+S(b)==2;}
template<class T1,class T2,class T3>bool S(T1&a,T2&b,T3&c){return S(a)+S(b)+S(c)==3;}
template<class T1,class T2,class T3,class T4>bool S(T1&a,T2&b,T3&c,T4&d){return S(a)+S(b)+S(c)+S(d)==4;}
template<class T1,class T2,class T3,class T4,class T5>bool S(T1&a,T2&b,T3&c,T4&d,T5&e){return S(a)+S(b)+S(c)+S(d)+S(e)==5;}

template<class T1>void P(const T1&a){_P(a);pc(' ');}
template<class T1,class T2>void P(const T1&a,const T2&b){_P(a);pc(' ');_P(b);pc(' ');}
template<class T1>void PN(const T1&a){_P(a);NL}
template<class T1,class T2>void PN(const T1&a,const T2&b){_P(a);pc(' ');_P(b);NL}
template<class T1,class T2,class T3>void PN(const T1&a,const T2&b,const T3&c){_P(a);pc(' ');_P(b);pc(' ');_P(c);NL}
template<class T1,class T2,class T3,class T4>void PN(const T1&a,const T2&b,const T3&c,const T4&d){_P(a);pc(' ');_P(b);pc(' ');_P(c);pc(' ');_P(d);NL}
template<class T1,class T2,class T3,class T4,class T5>void PN(const T1&a,const T2&b,const T3&c,const T4&d,const T5&e){_P(a);pc(' ');_P(b);pc(' ');_P(c);pc(' ');_P(d);pc(' ');_P(e);NL}
void PS(int a){printf("%*s",a,"");}

template<class T>void SA(T*a,int n){FR(i,n)S(a[i]);}
template<class T>void PA(T*a,int n){FR(i,n){if(i)pc(' ');_P(a[i]);}NL}
template<class T>void PA(const T&x){FE(it,x){if(it!=x.begin())pc(' ');_P(*it);}NL}

int kase;
const double pi=4*atan(1.);
const double ep=1e-9;
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3fll;
const ll MOD=1000000007;
//}

int dp[1000015],sum[1000015];

int main(){
  SHOW_TIME
  int n;
  S(n);
  int t;
  FR(i,n){
    S(t);
    sum[t]++;
  }
  int res=0;
  FOR(i,1000000){
    if(!sum[i]){
      continue;
    }
    dp[i]=max(dp[i],sum[i]);
    for(int j=i+i;j<=1000000;j+=i){
      if(!sum[j]){
        continue;
      }
      dp[j]=max(dp[j],dp[i]+sum[j]);
    }
    res=max(res,dp[i]);
  }
  PN(res);
}

/*********Risoft corporation all rights reserved*********/
/**************Template V2.32 build 20150719*************/

### Prompt

Develop a solution in CPP to the problem described below:

As you must know, the maximum clique problem in an arbitrary graph is NP-hard. Nevertheless, for some graphs of specific kinds it can be solved effectively.

Just in case, let us remind you that a clique in a non-directed graph is a subset of the vertices of a graph, such that any two vertices of this subset are connected by an edge. In particular, an empty set of vertexes and a set consisting of a single vertex, are cliques.

Let's define a divisibility graph for a set of positive integers A = {a1, a2, ..., an} as follows. The vertices of the given graph are numbers from set A, and two numbers ai and aj (i ≠ j) are connected by an edge if and only if either ai is divisible by aj, or aj is divisible by ai.

You are given a set of non-negative integers A. Determine the size of a maximum clique in a divisibility graph for set A.

Input

The first line contains integer n (1 ≤ n ≤ 106), that sets the size of set A.

The second line contains n distinct positive integers a1, a2, ..., an (1 ≤ ai ≤ 106) — elements of subset A. The numbers in the line follow in the ascending order.

Output

Print a single number — the maximum size of a clique in a divisibility graph for set A.

Examples

Input

8
3 4 6 8 10 18 21 24


Output

3

Note

In the first sample test a clique of size 3 is, for example, a subset of vertexes {3, 6, 18}. A clique of a larger size doesn't exist in this graph.

### Response

```cpp
/**************Powered by Graphene Richards**************/
//{

#define FLOAT_PRECISION     2

#ifdef _MSC_VER
#define _SECURE_SCL 0
#pragma comment(linker,"/STACK:102400000,102400000")
#else
#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
#endif
#if defined(_MSC_VER)||__cplusplus>199711L
#define IT(x) auto
#define DIT(x) auto
#else
#define IT(x) __typeof((x).begin())
#define DIT(x) __typeof((x).rbegin())
#endif

#  inc\
lude<cmath>
#  inc\
lude<cstdio>
#  inc\
lude<cstdlib>
#  inc\
lude<cstring>
#  inc\
lude<algorithm>
#  inc\
lude<bitset>
#  inc\
lude<complex>
#  inc\
lude<vector>
#  inc\
lude<iomanip>
#  inc\
lude<iostream>
#  inc\
lude<list>
#  inc\
lude<map>
#  inc\
lude<queue>
#  inc\
lude<set>
#  inc\
lude<stack>
#  inc\
lude<string>
#define FAST_RW ios_base::sync_with_stdio(0),cin.tie(0);
#define FS(i,a) for(ll i=0;a[i];i++)
#define FE(x,ctn) for(IT(ctn) x=(ctn).begin(),_en=(ctn).end();x!=_en;x++)
#define EF(x,ctn) for(DIT(ctn) x=(ctn).rbegin(),_en=(ctn).rend();x!=_en;x++)
#define FR(i,en) for(ll i=0,_en=(en);i<_en;i++)
#define FOR(i,en) for(ll i=1,_en=(en);i<=_en;i++)
#define RF(i,en) for(ll i=(en)-1;i>=0;i--)
#define ROF(i,en) for(ll i=(en);i>0;i--)
#define FFR(i,x,y) for(ll i=(x),_en=(y);i<=_en;i++)
#define RFF(i,x,y) for(ll i=(x),_en=(y);i>=_en;i--)
#define pc putchar
#define pb push_back
#define ppb pop_back
#define pq priority_queue
#define fi first
#define se second
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sqr(x) ((x)*(x))
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define clr(x) memset((x),0,sizeof(x))
#define ms(x,v) memset((x),(v),sizeof(x))
#define mc(x,y) memcpy((x),(y),sizeof(y))
#define NL puts("");
#define LB lower_bound
#define UB upper_bound
#define rand() ((rand()<<16)^(rand()<<15)^(rand()))
#ifdef _WIN32
#define _i64_ "%I\
64d"
#define _u64_ "%I\
64u"
#else
#define _i64_ "%l\
ld"
#define _u64_ "%l\
lu"
#endif
typedef unsigned ui;
typedef long long ll;
typedef unsigned long long ull;
typedef long double lf;
using namespace std;

ull gcd(ull a,ull b){if(!b)return a;while(b^=a^=b^=a%=b);return a;}

extern const ll MOD;
ll ksm(ll a,ll b){
  ll res=1;
  a%=MOD;
  for(;b;b>>=1){
    if(b&1)res=res*a%MOD;
    a=a*a%MOD;
  }
  return res;
}

#ifdef wmx16835
#include"wmx16835.h"
#else
#define LOG
#define TEL
#define test(...) 0
#define TEST(...) 0
#define TRY(...)
#define SF(...)
#define SC
#define PF
#define PC
#define PP
#define SHOW_TIME
#define BR
#endif

template<class T1,class T2,class T3>bool In(T1 x,T2 y,T3 z){return x<=y&&x>=z||x<=z&&x>=y;}
template<class T1,class T2>T1 max(const T1&a,const T2&b){return a<b?b:a;}
template<class T1,class T2,class T3>T1 max3(const T1&a,const T2&b,const T3&c){return a<b?(b<c?c:b):(a<c?c:a);}
template<class T1,class T2>T1 min(const T1&a,const T2&b){return a<b?a:b;}
template<class T1,class T2,class T3>T1 min3(const T1&a,const T2&b,const T3&c){return a<b?(a<c?a:c):(b<c?b:c);}

bool S(char*a){return scanf("%s",a)==1;}
bool S(int&a){return scanf("%d",&a)==1;}
bool S(bool&a){return scanf("%d",&a)==1;}
bool S(ui&a){return scanf("%u",&a)==1;}
bool S(float&a){return scanf("%f",&a)==1;}
bool S(double&a){return scanf("%lf",&a)==1;}
bool S(ll&a){return scanf(_i64_,&a)==1;}
bool S(ull&a){return scanf(_u64_,&a)==1;}
bool S(lf&a){double b;if(scanf("%lf",&b)==-1)return 0;a=b;return 1;}
bool S(char&a){char b[2];if(scanf("%1s",b)==-1)return 0;a=*b;return 1;}
bool SL(char*a){a[0]=0;while(gets(a)&&!a[0]);return a[0];}
template<class T1,class T2>bool S(pair<T1,T2>&a){S(a.fi),S(a.se);}
template<class T>bool S(T&a){a.in();}

void _P(const int&x){printf("%d",x);}
void _P(const bool&x){printf("%d",x);}
void _P(const ui&x){printf("%u",x);}
void _P(const char&x){printf("%c",x);}
void _P(const char*x){printf("%s",x);}
void _P(const string&x){printf("%s",x.c_str());}
void _P(const ll&x){printf(_i64_,x);}
void _P(const ull&x){printf(_u64_,x);}
void _P(const float&x){printf("%.*f",FLOAT_PRECISION,x);}
void _P(const double&x){printf("%.*f",FLOAT_PRECISION,x);}
void _P(const lf&x){printf("%.*f",FLOAT_PRECISION,(double)x);}
template<class T1,class T2>void _P(const pair<T1,T2>&x){_P(x.fi);pc(' ');_P(x.se);}
template<class T>void _P(const T&a){a.out();}

template<class T1,class T2>bool S(T1&a,T2&b){return S(a)+S(b)==2;}
template<class T1,class T2,class T3>bool S(T1&a,T2&b,T3&c){return S(a)+S(b)+S(c)==3;}
template<class T1,class T2,class T3,class T4>bool S(T1&a,T2&b,T3&c,T4&d){return S(a)+S(b)+S(c)+S(d)==4;}
template<class T1,class T2,class T3,class T4,class T5>bool S(T1&a,T2&b,T3&c,T4&d,T5&e){return S(a)+S(b)+S(c)+S(d)+S(e)==5;}

template<class T1>void P(const T1&a){_P(a);pc(' ');}
template<class T1,class T2>void P(const T1&a,const T2&b){_P(a);pc(' ');_P(b);pc(' ');}
template<class T1>void PN(const T1&a){_P(a);NL}
template<class T1,class T2>void PN(const T1&a,const T2&b){_P(a);pc(' ');_P(b);NL}
template<class T1,class T2,class T3>void PN(const T1&a,const T2&b,const T3&c){_P(a);pc(' ');_P(b);pc(' ');_P(c);NL}
template<class T1,class T2,class T3,class T4>void PN(const T1&a,const T2&b,const T3&c,const T4&d){_P(a);pc(' ');_P(b);pc(' ');_P(c);pc(' ');_P(d);NL}
template<class T1,class T2,class T3,class T4,class T5>void PN(const T1&a,const T2&b,const T3&c,const T4&d,const T5&e){_P(a);pc(' ');_P(b);pc(' ');_P(c);pc(' ');_P(d);pc(' ');_P(e);NL}
void PS(int a){printf("%*s",a,"");}

template<class T>void SA(T*a,int n){FR(i,n)S(a[i]);}
template<class T>void PA(T*a,int n){FR(i,n){if(i)pc(' ');_P(a[i]);}NL}
template<class T>void PA(const T&x){FE(it,x){if(it!=x.begin())pc(' ');_P(*it);}NL}

int kase;
const double pi=4*atan(1.);
const double ep=1e-9;
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3fll;
const ll MOD=1000000007;
//}

int dp[1000015],sum[1000015];

int main(){
  SHOW_TIME
  int n;
  S(n);
  int t;
  FR(i,n){
    S(t);
    sum[t]++;
  }
  int res=0;
  FOR(i,1000000){
    if(!sum[i]){
      continue;
    }
    dp[i]=max(dp[i],sum[i]);
    for(int j=i+i;j<=1000000;j+=i){
      if(!sum[j]){
        continue;
      }
      dp[j]=max(dp[j],dp[i]+sum[j]);
    }
    res=max(res,dp[i]);
  }
  PN(res);
}

/*********Risoft corporation all rights reserved*********/
/**************Template V2.32 build 20150719*************/

```