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 prime[10001], tp;
bool isp[10001];
int ish[10000001];
int num[10000001];
int yin[21], ty;
int fa[10000001];
int n;
void prime_cal() {
  memset(isp, 0, sizeof(isp));
  tp = 0;
  for (int i = 2; i < 10001; ++i) {
    if (!isp[i]) prime[tp++] = i;
    for (int j = 0; j < tp && i * prime[j] < 10001; ++j) {
      isp[i * prime[j]] = 1;
      if (i % prime[j] == 0) break;
    }
  }
}
void yin_cal(int num) {
  ty = 0;
  int limit = (int)sqrt((double)(num));
  for (int i = 0; i < tp && prime[i] <= limit && prime[i] <= num; ++i)
    if (num % prime[i] == 0) {
      yin[ty] = 1;
      while (num % prime[i] == 0) yin[ty] *= prime[i], num /= prime[i];
      ++ty;
    }
  if (num > 1) yin[ty++] = num;
}
void hebing(int x, int y) {
  while (fa[x] != -1) x = fa[x];
  while (fa[y] != -1) y = fa[y];
  if (x != y) fa[x] = y;
}
int renew(int x) {
  if (fa[x] == -1) return x;
  return fa[x] = renew(fa[x]);
}
void yin_div(int x, int cur, const int &l, int w) {
  if (cur == ty) {
    int y = num[l] / x;
    if (num[l] % 2) {
      int r, s, pos = 0;
      long long nm;
      if (x < y) swap(x, y);
      r = (x + y) / 2;
      s = (x - y) / 2;
      if ((r + s) % 2 == 0) return;
      nm = 2 * (long long)r * s;
      if (nm < 10000001 && ish[nm] != -1) {
        hebing(l, ish[nm]);
        renew(l);
        renew(ish[nm]);
      }
      nm = (long long)r * r + (long long)s * s;
      if (nm < 10000001 && ish[nm] != -1) {
        hebing(l, ish[nm]);
        renew(l);
        renew(ish[nm]);
      }
    } else {
      int pos = 0;
      long long nm;
      if (x % 4 && y % 4) return;
      if (x % 2 == 0)
        x /= 2;
      else
        y /= 2;
      if (x < y) swap(x, y);
      nm = (long long)x * x - (long long)y * y;
      if (nm < 10000001 && ish[nm] != -1) {
        hebing(l, ish[nm]);
        renew(l);
        renew(ish[nm]);
      }
      nm = (long long)x * x + (long long)y * y;
      if (nm < 10000001 && ish[nm] != -1) {
        hebing(l, ish[nm]);
        renew(l);
        renew(ish[nm]);
      }
    }
    return;
  }
  for (int i = cur; i < ty; ++i)
    yin_div(x *= (w ? yin[i] : 1), i + 1, l, w ^ 1);
}
void solve() {
  memset(ish, 255, sizeof(ish));
  for (int i = 0; i < n; ++i) ish[num[i]] = i;
  memset(fa, 255, sizeof(fa));
  for (int i = 0; i < n; ++i) {
    yin_cal(num[i]);
    for (int j = 0; j <= ty; ++j) yin_div(1, j, i, 1);
  }
  int ans = 0;
  for (int i = 0; i < n; ++i) ans += fa[i] == -1;
  printf("%d\n", ans);
}
int main() {
  prime_cal();
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) scanf("%d", &num[i]);
  solve();
  return 0;
}