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[10000001], h[10000001], g[10000001], sz[10000001];
bool united[10000001], was[10000001];
long long gcd(long long a, long long b) {
  if (a < b) swap(a, b);
  while (b) {
    a %= b;
    swap(a, b);
  }
  return a;
}
int find_set(int v) { return p[v] == v ? v : p[v] = find_set(p[v]); }
void union_set(int u, int v) {
  u = find_set(u);
  v = find_set(v);
  if (u == v) return;
  united[u] = united[v] = true;
  if (h[u] < h[v]) swap(u, v);
  sz[u] += sz[v];
  p[v] = u;
  if (h[u] == h[v]) ++h[u];
}
int main() {
  ios_base::sync_with_stdio(false);
  int t, in;
  cin >> t;
  for (int i(0); i < t; ++i) {
    cin >> in;
    ++g[in];
  }
  for (int i(1); i < 10000001; ++i) p[i] = i, sz[i] = g[i];
  for (long long n(1); n * n < 2 * 10000001; ++n)
    for (long long m(n + 1); m * m + n * n < 10000001 || 2 * m * n < 10000001;
         ++ ++m)
      if (gcd(n, m) == 1) {
        long long x(n * n + m * m), y(2 * n * m), z(m * m - n * n);
        if (x >= 10000001) x = 0;
        if (y >= 10000001) y = 0;
        if (z >= 10000001) z = 0;
        if (x && y && g[x] && g[y]) union_set(x, y);
        if (y && z && g[y] && g[z]) union_set(y, z);
        if (x && z && g[x] && g[z]) union_set(x, z);
      }
  int ans(0), s;
  for (int i(1); i < 10000001; ++i)
    if (g[i]) {
      s = find_set(i);
      if (!was[s]) {
        was[s] = true;
        if (united[i])
          ++ans;
        else
          ans += g[i];
      }
    }
  cout << ans;
}