Problem: Misha decided to help Pasha and Akim be friends again. He had a cunning plan — to destroy all the laughy mushrooms. He knows that the laughy mushrooms can easily burst when they laugh. Mushrooms grow on the lawns. There are a[t] mushrooms on the t-th lawn.

Misha knows that the lawns where the mushrooms grow have a unique ability. A lawn (say, i) can transfer laugh to other lawn (say, j) if there exists an integer (say, b) such, that some permutation of numbers a[i], a[j] and b is a beautiful triple (i ≠ j). A beautiful triple is such three pairwise coprime numbers x, y, z, which satisfy the following condition: x2 + y2 = z2.

Misha wants to know on which minimal number of lawns he should laugh for all the laughy mushrooms to burst.

Input

The first line contains one integer n (1 ≤ n ≤ 106) which is the number of lawns. The next line contains n integers ai which are the number of mushrooms on the i-lawn (1 ≤ ai ≤ 107). All the numbers are different.

Output

Print a single number — the minimal number of lawns on which Misha should laugh for all the mushrooms to burst.

Examples

Input

1
2


Output

1


Input

2
1 2


Output

2


Input

2
3 5


Output

1

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
int P[10000005], A[10000005], np;
void criba() {
  for (int i = 2; i < 10000005; i++) {
    if (!A[i]) P[A[i] = ++np] = i;
    for (int j = 1; j <= A[i] && P[j] * i < 10000005; j++) A[P[j] * i] = j;
  }
}
long long pa[30], sz;
int x[1000005], n;
vector<int> E[1000005];
int pos[10000005];
int cola[1000005], qi, qf;
int vis[1000005];
int xx, par, ind;
void add(int i, int j) {
  E[i].push_back(j);
  E[j].push_back(i);
}
void solve(int ss = 0, long long d = 1) {
  if (ss == sz) {
    if (xx > 5000 * d) return;
    d = d * d;
    if (xx <= d) return;
    long long x2 = (long long)xx * xx;
    long long d2 = (long long)d * d;
    if (par) {
      if (x2 > d2) {
        long long z = (x2 + d2) / d;
        if (z < 10000005 && ~pos[z] && z % 2) add(ind, pos[z]);
        z = (x2 - d2) / d;
        if (z < 10000005 && ~pos[z] && z % 2) add(ind, pos[z]);
      }
    } else {
      if (x2 > d2) {
        long long z = (x2 + d2) / d / 2;
        if (z < 10000005 && ~pos[z] && z % 2) add(ind, pos[z]);
        z = (x2 - d2) / d / 2;
        if (z < 10000005 && ~pos[z] && z % 2) add(ind, pos[z]);
      }
    }
    return;
  }
  solve(ss + 1, d);
  solve(ss + 1, d * pa[ss]);
}
int main() {
  criba();
  cin >> n;
  memset(pos, -1, sizeof pos);
  for (int i = 0; i < n; i++) scanf("%d", x + i), pos[x[i]] = i;
  for (int i = 0; i < n; i++) {
    sz = 0;
    xx = x[i];
    par = 0;
    ind = i;
    if (xx % 2 == 0) xx /= 2, par = 1;
    int _xx = xx;
    while (xx > 1) {
      int p = P[A[xx]];
      int pot = 1;
      for (; xx % p == 0; xx /= p) pot *= p;
      pa[sz++] = pot;
    }
    xx = _xx;
    solve();
  }
  int res = 0;
  for (int i = 0; i < n; i++)
    if (vis[i] == 0) {
      res++;
      qi = qf = 0;
      vis[cola[qf++] = i] = 1;
      while (qi < qf) {
        int q = cola[qi++];
        for (typeof E[q].begin() j = E[q].begin(); j != E[q].end(); j++)
          if (vis[*j] == 0) {
            vis[cola[qf++] = *j] = 1;
          }
      }
    }
  cout << res << endl;
}