#include <bits/stdc++.h>
using namespace std;
namespace maxmin {
template <class T>
T max(T&& a) {
  return a;
}
template <class T>
T min(T&& a) {
  return a;
}
template <class T>
T max(T&& a, T&& b) {
  return a > b ? a : b;
}
template <class T>
T min(T&& a, T&& b) {
  return a < b ? a : b;
}
template <class T, class... Ts>
T max(T&& a, Ts&&... ts) {
  T b = max(ts...);
  return a > b ? a : b;
}
template <class T, class... Ts>
T min(T&& a, Ts&&... ts) {
  T b = min(ts...);
  return a < b ? a : b;
}
template <class T, class... Ts>
T chmax(T&& a, Ts&&... ts) {
  a = max(a, ts...);
  return a;
}
template <class T, class... Ts>
T chmin(T&& a, Ts&&... ts) {
  a = min(a, ts...);
  return a;
}
}  // namespace maxmin
namespace input {
template <class T>
void re(T&& x) {
  cin >> x;
}
template <class T1, class T2>
void re(pair<T1, T2>& p) {
  re(p.first);
  re(p.second);
}
template <class T>
void re(vector<T>& a) {
  for (int i = 0; i < (int)(a).size(); i++) re(a[i]);
}
template <class T1, class T2>
void rea(T1&& a, T2 t) {
  for (int i = 0; i < t; i++) re(a[i]);
}
template <class T1, class T2, class... Ts>
void rea(T1&& a, T2 t, Ts&&... ts) {
  rea(a, t);
  rea(ts...);
}
template <class T1, class T2>
void rea1(T1&& a, T2 t) {
  for (int i = 1; i <= t; i++) re(a[i]);
}
template <class T1, class T2, class... Ts>
void rea1(T1&& a, T2 t, Ts&... ts) {
  rea1(a, t);
  rea1(ts...);
}
template <class T, class... Ts>
void re(T&& t, Ts&... ts) {
  re(t);
  re(ts...);
}
}  // namespace input
namespace output {
void pr(int x) { cout << x; }
void pr(bool x) { cout << x; }
void pr(long long x) { cout << x; }
void pr(long long unsigned x) { cout << x; }
void pr(double x) { cout << x; }
void pr(char x) { cout << x; }
void pr(const string& x) { cout << x; }
void pr(const char* x) { cout << x; }
void pr(const char* x, size_t len) { cout << string(x, len); }
void ps() { cout << "\n"; }
void pn() {}
void pw() { pr(" "); }
void pc() {
  pr("]");
  ps();
}
template <class T>
void pr(const T&);
bool parse(const char* t) {
  if (t == "\n") return true;
  return false;
}
template <class T>
bool parse(T&& t) {
  return false;
}
template <class T1, class T2>
bool parsepair(const pair<T1, T2>& x) {
  return true;
}
template <class T>
bool parsepair(T&& t) {
  return false;
}
template <class T1, class T2>
void psa(T1&& a, T2 t) {
  for (int i = 0; i < t; i++) pr(a[i]), pw();
  ps();
}
template <class T1, class T2>
void psa2(T1&& a, T2 t1, T2 t2) {
  for (int i = 0; i < t1; i++) {
    for (int j = 0; j < t2; j++) pr(a[i][j]), pw();
    ps();
  }
}
template <class T1, class T2>
void pr(const pair<T1, T2>& x) {
  pr(x.first);
  pw();
  pr(x.second);
}
template <class T>
void pr(const T& x) {
  bool fst = 1;
  bool op = 0;
  if (parsepair(*x.begin())) op = 1;
  for (const auto& a : x) {
    if (!fst) pw();
    if (op) pr("{");
    pr(a), fst = 0;
    if (op) pr("}");
  }
}
template <class T, class... Ts>
void pr(const T& t, const Ts&... ts) {
  pr(t);
  pr(ts...);
}
template <class T, class... Ts>
void ps(const T& t, const Ts&... ts) {
  pr(t);
  if (sizeof...(ts)) {
    if (!parse(t)) pw();
  }
  ps(ts...);
}
template <class T>
void pn(const T& t) {
  for (const auto& a : t) ps(a);
}
template <class T, class... Ts>
void pw(const T& t, const Ts&... ts) {
  pr(t);
  if (sizeof...(ts)) pw();
  pw(ts...);
}
template <class T, class... Ts>
void pc(const T& t, const Ts&... ts) {
  bool op = 0;
  if (parsepair(t)) op = 1;
  if (op) pr("{");
  pr(t);
  if (op) pr("}");
  if (sizeof...(ts)) pr(", ");
  pc(ts...);
}
namespace trace {
template <class T1, class T2>
void __f(const char* name, const T1& x, const T2& y) {
  pr("[", y, "] = ");
  ps(x);
}
template <class T1, class T2, class... Ts>
void __f(const char* name, const T1& x, const T2& y, const Ts&... rest) {
  const char* open = strchr(name, '[');
  pr("[", y, "]");
  __f(open + 1, x, rest...);
}
template <class T1, class T2, class... Ts>
void __f0(const char* name, const T1& x, const T2& y, const Ts&... rest) {
  const char* open = strchr(name, '[');
  pr(name, size_t(open - name));
  __f(name, x, y, rest...);
}
template <class T>
void __fn(int n, const char* name, const T& x) {
  for (int i = 0; i < n; i++) pr(name), __f(name, x[i], i);
}
}  // namespace trace
}  // namespace output
using namespace maxmin;
using namespace input;
using namespace output;
using namespace output::trace;
using ll = long long;
using pii = pair<int, int>;
const int N = 1e5 + 5;
int a[N], n, dp[N], d[N];
vector<int> primes[N];
vector<bool> prime;
void sieve(int maxn) {
  int i, j;
  prime.assign(maxn + 1, true);
  prime[0] = prime[1] = false;
  for (i = 2; i <= maxn; i += 2) {
    prime[i] = i == 2;
    primes[i].push_back(2);
  }
  for (i = 3; i <= maxn; i += 2) {
    if (prime[i]) {
      for (j = i; j <= maxn; j += i) {
        if (prime[j]) prime[j] = false;
        primes[j].push_back(i);
      }
    }
  }
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  int i, ans = 1;
  re(n);
  rea(a, n);
  sieve(N - 2);
  for (i = 0; i < n; i++) {
    for (auto& x : primes[a[i]]) chmax(dp[i], d[x] + 1);
    for (auto& x : primes[a[i]]) chmax(d[x], dp[i]);
    chmax(ans, dp[i]);
  }
  ps(ans);
  return 0;
}

### Prompt

Develop a solution in Cpp to the problem described below:

Squirrel Liss is interested in sequences. She also has preferences of integers. She thinks n integers a1, a2, ..., an are good.

Now she is interested in good sequences. A sequence x1, x2, ..., xk is called good if it satisfies the following three conditions:

  * The sequence is strictly increasing, i.e. xi < xi + 1 for each i (1 ≤ i ≤ k - 1). 
  * No two adjacent elements are coprime, i.e. gcd(xi, xi + 1) > 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.

Input

The input consists of two lines. The first line contains a single integer n (1 ≤ n ≤ 105) — the number of good integers. The second line contains a single-space separated list of good integers a1, a2, ..., an in strictly increasing order (1 ≤ ai ≤ 105; ai < ai + 1).

Output

Print a single integer — the length of the longest good sequence.

Examples

Input

5
2 3 4 6 9


Output

4


Input

9
1 2 3 5 6 7 8 9 10


Output

4

Note

In the first example, the following sequences are examples of good sequences: [2; 4; 6; 9], [2; 4; 6], [3; 9], [6]. The length of the longest good sequence is 4.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
namespace maxmin {
template <class T>
T max(T&& a) {
  return a;
}
template <class T>
T min(T&& a) {
  return a;
}
template <class T>
T max(T&& a, T&& b) {
  return a > b ? a : b;
}
template <class T>
T min(T&& a, T&& b) {
  return a < b ? a : b;
}
template <class T, class... Ts>
T max(T&& a, Ts&&... ts) {
  T b = max(ts...);
  return a > b ? a : b;
}
template <class T, class... Ts>
T min(T&& a, Ts&&... ts) {
  T b = min(ts...);
  return a < b ? a : b;
}
template <class T, class... Ts>
T chmax(T&& a, Ts&&... ts) {
  a = max(a, ts...);
  return a;
}
template <class T, class... Ts>
T chmin(T&& a, Ts&&... ts) {
  a = min(a, ts...);
  return a;
}
}  // namespace maxmin
namespace input {
template <class T>
void re(T&& x) {
  cin >> x;
}
template <class T1, class T2>
void re(pair<T1, T2>& p) {
  re(p.first);
  re(p.second);
}
template <class T>
void re(vector<T>& a) {
  for (int i = 0; i < (int)(a).size(); i++) re(a[i]);
}
template <class T1, class T2>
void rea(T1&& a, T2 t) {
  for (int i = 0; i < t; i++) re(a[i]);
}
template <class T1, class T2, class... Ts>
void rea(T1&& a, T2 t, Ts&&... ts) {
  rea(a, t);
  rea(ts...);
}
template <class T1, class T2>
void rea1(T1&& a, T2 t) {
  for (int i = 1; i <= t; i++) re(a[i]);
}
template <class T1, class T2, class... Ts>
void rea1(T1&& a, T2 t, Ts&... ts) {
  rea1(a, t);
  rea1(ts...);
}
template <class T, class... Ts>
void re(T&& t, Ts&... ts) {
  re(t);
  re(ts...);
}
}  // namespace input
namespace output {
void pr(int x) { cout << x; }
void pr(bool x) { cout << x; }
void pr(long long x) { cout << x; }
void pr(long long unsigned x) { cout << x; }
void pr(double x) { cout << x; }
void pr(char x) { cout << x; }
void pr(const string& x) { cout << x; }
void pr(const char* x) { cout << x; }
void pr(const char* x, size_t len) { cout << string(x, len); }
void ps() { cout << "\n"; }
void pn() {}
void pw() { pr(" "); }
void pc() {
  pr("]");
  ps();
}
template <class T>
void pr(const T&);
bool parse(const char* t) {
  if (t == "\n") return true;
  return false;
}
template <class T>
bool parse(T&& t) {
  return false;
}
template <class T1, class T2>
bool parsepair(const pair<T1, T2>& x) {
  return true;
}
template <class T>
bool parsepair(T&& t) {
  return false;
}
template <class T1, class T2>
void psa(T1&& a, T2 t) {
  for (int i = 0; i < t; i++) pr(a[i]), pw();
  ps();
}
template <class T1, class T2>
void psa2(T1&& a, T2 t1, T2 t2) {
  for (int i = 0; i < t1; i++) {
    for (int j = 0; j < t2; j++) pr(a[i][j]), pw();
    ps();
  }
}
template <class T1, class T2>
void pr(const pair<T1, T2>& x) {
  pr(x.first);
  pw();
  pr(x.second);
}
template <class T>
void pr(const T& x) {
  bool fst = 1;
  bool op = 0;
  if (parsepair(*x.begin())) op = 1;
  for (const auto& a : x) {
    if (!fst) pw();
    if (op) pr("{");
    pr(a), fst = 0;
    if (op) pr("}");
  }
}
template <class T, class... Ts>
void pr(const T& t, const Ts&... ts) {
  pr(t);
  pr(ts...);
}
template <class T, class... Ts>
void ps(const T& t, const Ts&... ts) {
  pr(t);
  if (sizeof...(ts)) {
    if (!parse(t)) pw();
  }
  ps(ts...);
}
template <class T>
void pn(const T& t) {
  for (const auto& a : t) ps(a);
}
template <class T, class... Ts>
void pw(const T& t, const Ts&... ts) {
  pr(t);
  if (sizeof...(ts)) pw();
  pw(ts...);
}
template <class T, class... Ts>
void pc(const T& t, const Ts&... ts) {
  bool op = 0;
  if (parsepair(t)) op = 1;
  if (op) pr("{");
  pr(t);
  if (op) pr("}");
  if (sizeof...(ts)) pr(", ");
  pc(ts...);
}
namespace trace {
template <class T1, class T2>
void __f(const char* name, const T1& x, const T2& y) {
  pr("[", y, "] = ");
  ps(x);
}
template <class T1, class T2, class... Ts>
void __f(const char* name, const T1& x, const T2& y, const Ts&... rest) {
  const char* open = strchr(name, '[');
  pr("[", y, "]");
  __f(open + 1, x, rest...);
}
template <class T1, class T2, class... Ts>
void __f0(const char* name, const T1& x, const T2& y, const Ts&... rest) {
  const char* open = strchr(name, '[');
  pr(name, size_t(open - name));
  __f(name, x, y, rest...);
}
template <class T>
void __fn(int n, const char* name, const T& x) {
  for (int i = 0; i < n; i++) pr(name), __f(name, x[i], i);
}
}  // namespace trace
}  // namespace output
using namespace maxmin;
using namespace input;
using namespace output;
using namespace output::trace;
using ll = long long;
using pii = pair<int, int>;
const int N = 1e5 + 5;
int a[N], n, dp[N], d[N];
vector<int> primes[N];
vector<bool> prime;
void sieve(int maxn) {
  int i, j;
  prime.assign(maxn + 1, true);
  prime[0] = prime[1] = false;
  for (i = 2; i <= maxn; i += 2) {
    prime[i] = i == 2;
    primes[i].push_back(2);
  }
  for (i = 3; i <= maxn; i += 2) {
    if (prime[i]) {
      for (j = i; j <= maxn; j += i) {
        if (prime[j]) prime[j] = false;
        primes[j].push_back(i);
      }
    }
  }
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  int i, ans = 1;
  re(n);
  rea(a, n);
  sieve(N - 2);
  for (i = 0; i < n; i++) {
    for (auto& x : primes[a[i]]) chmax(dp[i], d[x] + 1);
    for (auto& x : primes[a[i]]) chmax(d[x], dp[i]);
    chmax(ans, dp[i]);
  }
  ps(ans);
  return 0;
}

```