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>
const int N = 1000000 + 10;
const int M = 10000000 + 10;
int n, m;
bool c[M];
int fa[M], size[M];
inline void read(int &x) {
  char ch;
  do ch = getchar();
  while (ch < '0' or ch > '9');
  x = 0;
  while (ch >= '0' and ch <= '9') {
    x = (x << 3) + (x << 1) + (ch & 15);
    ch = getchar();
  }
}
int gf(int x) { return (x ^ fa[x]) ? (fa[x] = gf(fa[x])) : x; }
int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }
bool merge(int x, int y) {
  x = gf(x);
  y = gf(y);
  if (x ^ y) {
    if (size[x] < size[y]) std::swap(x, y);
    size[x] += size[y];
    fa[y] = x;
    return true;
  } else
    return false;
}
int main() {
  int i, x, y;
  long long x1, x2, x3;
  int ans;
  read(n);
  for (i = 1; i <= n; i++) {
    read(x);
    c[x] = true;
    m = std::max(m, x);
  }
  for (i = 1; i <= m; i++) {
    fa[i] = i;
    size[i] = 1;
  }
  ans = n;
  for (y = 2; y <= m; y++) {
    for (x = 1 + (y & 1); x < y and (x2 = 2 * x * y) <= m; x += 2) {
      if (gcd(x, y) > 1) continue;
      x1 = 1LL * y * y - 1LL * x * x;
      x3 = 1LL * y * y + 1LL * x * x;
      if (x1 <= m and c[x1] and c[x2]) ans -= merge(x1, x2);
      if (x3 <= m and c[x2] and c[x3]) ans -= merge(x2, x3);
      if (x1 <= m and x3 <= m and c[x1] and c[x3]) ans -= merge(x1, x3);
    }
  }
  printf("%d\n", ans);
  return 0;
}