#include <bits/stdc++.h>
using namespace std;
void input(vector<long long int> &arr) {
  for (int i = 0; i < arr.size(); i++) cin >> arr[i];
}
void output(vector<long long int> arr) {
  for (int i = 0; i < arr.size(); i++) cout << arr[i] << " ";
  cout << "\n";
}
long long int gcd(long long int a, long long int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long int power(long long int a, long long int b) {
  if (b == 0) return 1;
  if (b == 1) return a;
  long long int smallans = power(a, b / 2);
  long long int myans = (smallans * smallans) % 1000000007;
  if ((b & 1)) myans = (myans * a) % 1000000007;
  return myans;
}
long long int multiply(long long int a, long long int b) {
  long long int ans = ((a % 1000000007) * (b % 1000000007)) % 1000000007;
  return ans;
}
long long int add(long long int a, long long int b) {
  long long int ans = ((a % 1000000007) + (b % 1000000007)) % 1000000007;
  return ans;
}
long long int subtract(long long int a, long long int b) {
  long long int ans = ((a % 1000000007) - (b % 1000000007)) % 1000000007;
  if (ans < 0) ans += 1000000007;
  return ans;
}
long long int divide(long long int a, long long int b) {
  return multiply(a, power(b, 1000000007 - 2));
}
struct hash_pair {
  template <class T1, class T2>
  size_t operator()(const pair<T1, T2> &p) const {
    auto hash1 = hash<T1>{}(p.first);
    auto hash2 = hash<T2>{}(p.second);
    return hash1 ^ hash2;
  }
};
void update(vector<long long int> &tree, long long int index,
            long long int val) {
  index++;
  while (index < tree.size()) {
    tree[index] = (tree[index] + val) % 1000000007;
    index += index & (-index);
  }
}
long long int calculate(vector<long long int> &tree, long long int index) {
  long long int sum = 0;
  index++;
  while (index > 0) {
    sum = (sum + tree[index]) % 1000000007;
    index -= index & (-index);
  }
  return sum;
}
long long int findpar(long long int p, vector<long long int> &parent) {
  if (parent[p] == p) return p;
  parent[p] = findpar(parent[p], parent);
  return parent[p];
}
void merge(long long int a, long long int b, vector<long long int> &parent,
           vector<long long int> &size_) {
  a = findpar(a, parent);
  b = findpar(b, parent);
  if (a != b) {
    if (size_[a] < size_[b]) swap(a, b);
    parent[b] = a;
    size_[a] += size_[b];
  }
}
void sieve(vector<bool> &primes, vector<vector<long long int> > &count) {
  for (long long int i = 2; i < primes.size(); i++) {
    if (primes[i]) {
      for (long long int j = i; j < primes.size(); j += i) {
        primes[j] = false;
        count[j].push_back(i);
      }
    }
  }
}
void solve() {
  long long int n;
  cin >> n;
  vector<long long int> arr(n, 0);
  input(arr);
  vector<vector<long long int> > primes(100001);
  vector<bool> nums(100001, true);
  sieve(nums, primes);
  vector<long long int> count(1e5 + 1, 0);
  for (int i = 0; i < n; i++) {
    long long int maxans = 0;
    for (int j = 0; j < primes[arr[i]].size(); j++) {
      maxans = max(maxans, count[primes[arr[i]][j]]);
    }
    maxans++;
    for (int j = 0; j < primes[arr[i]].size(); j++) {
      count[primes[arr[i]][j]] = maxans;
    }
  }
  long long int ans = 0;
  for (int i = 0; i < 1e5 + 1; i++) ans = max(ans, count[i]);
  long long int one = 1;
  cout << max(one, ans) << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int t = 1;
  while (t--) {
    solve();
  }
  return 0;
}

### Prompt

Please formulate a CPP solution to the following problem:

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;
void input(vector<long long int> &arr) {
  for (int i = 0; i < arr.size(); i++) cin >> arr[i];
}
void output(vector<long long int> arr) {
  for (int i = 0; i < arr.size(); i++) cout << arr[i] << " ";
  cout << "\n";
}
long long int gcd(long long int a, long long int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long int power(long long int a, long long int b) {
  if (b == 0) return 1;
  if (b == 1) return a;
  long long int smallans = power(a, b / 2);
  long long int myans = (smallans * smallans) % 1000000007;
  if ((b & 1)) myans = (myans * a) % 1000000007;
  return myans;
}
long long int multiply(long long int a, long long int b) {
  long long int ans = ((a % 1000000007) * (b % 1000000007)) % 1000000007;
  return ans;
}
long long int add(long long int a, long long int b) {
  long long int ans = ((a % 1000000007) + (b % 1000000007)) % 1000000007;
  return ans;
}
long long int subtract(long long int a, long long int b) {
  long long int ans = ((a % 1000000007) - (b % 1000000007)) % 1000000007;
  if (ans < 0) ans += 1000000007;
  return ans;
}
long long int divide(long long int a, long long int b) {
  return multiply(a, power(b, 1000000007 - 2));
}
struct hash_pair {
  template <class T1, class T2>
  size_t operator()(const pair<T1, T2> &p) const {
    auto hash1 = hash<T1>{}(p.first);
    auto hash2 = hash<T2>{}(p.second);
    return hash1 ^ hash2;
  }
};
void update(vector<long long int> &tree, long long int index,
            long long int val) {
  index++;
  while (index < tree.size()) {
    tree[index] = (tree[index] + val) % 1000000007;
    index += index & (-index);
  }
}
long long int calculate(vector<long long int> &tree, long long int index) {
  long long int sum = 0;
  index++;
  while (index > 0) {
    sum = (sum + tree[index]) % 1000000007;
    index -= index & (-index);
  }
  return sum;
}
long long int findpar(long long int p, vector<long long int> &parent) {
  if (parent[p] == p) return p;
  parent[p] = findpar(parent[p], parent);
  return parent[p];
}
void merge(long long int a, long long int b, vector<long long int> &parent,
           vector<long long int> &size_) {
  a = findpar(a, parent);
  b = findpar(b, parent);
  if (a != b) {
    if (size_[a] < size_[b]) swap(a, b);
    parent[b] = a;
    size_[a] += size_[b];
  }
}
void sieve(vector<bool> &primes, vector<vector<long long int> > &count) {
  for (long long int i = 2; i < primes.size(); i++) {
    if (primes[i]) {
      for (long long int j = i; j < primes.size(); j += i) {
        primes[j] = false;
        count[j].push_back(i);
      }
    }
  }
}
void solve() {
  long long int n;
  cin >> n;
  vector<long long int> arr(n, 0);
  input(arr);
  vector<vector<long long int> > primes(100001);
  vector<bool> nums(100001, true);
  sieve(nums, primes);
  vector<long long int> count(1e5 + 1, 0);
  for (int i = 0; i < n; i++) {
    long long int maxans = 0;
    for (int j = 0; j < primes[arr[i]].size(); j++) {
      maxans = max(maxans, count[primes[arr[i]][j]]);
    }
    maxans++;
    for (int j = 0; j < primes[arr[i]].size(); j++) {
      count[primes[arr[i]][j]] = maxans;
    }
  }
  long long int ans = 0;
  for (int i = 0; i < 1e5 + 1; i++) ans = max(ans, count[i]);
  long long int one = 1;
  cout << max(one, ans) << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int t = 1;
  while (t--) {
    solve();
  }
  return 0;
}

```