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 long long MOD = 1e9 + 7, INF = 1e18 + 1;
using namespace std;
long long a[1000000], cnt, n, m;
long long p[1000000], sz[1000000];
int d[10000001];
long long gcd(long long a, long long b) {
  if (!b)
    return (a > 1);
  else
    return gcd(b, a % b);
}
long long find(long long x) {
  if (p[x] == x)
    return x;
  else
    return p[x] = find(p[x]);
}
void unite(long long a, long long b) {
  a = find(a);
  b = find(b);
  if (a == b) return;
  if (sz[a] < sz[b]) swap(a, b);
  p[b] = a;
  sz[a] += sz[b];
  cnt--;
}
int main() {
  cin >> n;
  for (long long i = 0; i < n; i++) {
    p[i] = i;
    sz[i] = 1;
  }
  memset(d, -1, sizeof(d));
  cnt = n;
  for (long long i = 0; i < n; i++) {
    scanf("%lld", &a[i]);
    d[a[i]] = i;
    m = max(m, a[i]);
  }
  for (long long y = 0; y <= m; y++)
    for (long long x = y + 1; x * x - y * y <= m && 2 * x * y <= m; x++) {
      long long x1 = x * x + y * y;
      long long x2 = 2 * x * y;
      long long x3 = x * x - y * y;
      if (gcd(x1, x2) || gcd(x2, x3) || gcd(x1, x3)) continue;
      if (x1 <= m && d[x1] >= 0 && d[x2] >= 0) unite(d[x1], d[x2]);
      if (x1 <= m && d[x1] >= 0 && d[x3] >= 0) unite(d[x1], d[x3]);
      if (d[x2] >= 0 && d[x3] >= 0) unite(d[x2], d[x3]);
    }
  cout << cnt;
}