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 JAVA):

Solution:
//package cf56d;

import java.util.*;
import java.math.*;

public class CF56D {
    static int MAXN = 1000000;
    static int MAX = 10000000;
    static int[] idx = new int[MAX + 1];
    static int[] pre = new int[MAXN];
    static int[] rank = new int[MAXN];
    static int[] a = new int[MAXN];
    static int ret;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i <= MAX; i++) idx[i] = -1;
        
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            pre[i] = i;
            rank[i] = 0;
        }
        for (int i = 0; i < n; i++) idx[a[i]] = i;
        
        ret = n;
        for (int c = 1; c <= MAX; c++)
          for (int b = c + 1; 2L * b * c <= MAX && 1L * b * b - 1L * c * c <= MAX; b++) if (gcd(c,b) == 1 && (c + b) % 2 > 0){
              int g1 = idx[b * b - c * c];
              int g2 = idx[2 * b * c];
              int g3 = -1;
              if (1L * b * b + 1L * c * c <= MAX) g3 = idx[b * b + c * c];
              if (g1 >= 0 && g2 >= 0) {
                  link(g1,g2);
              }
              if (g2 >= 0 && g3 >= 0) {
                  link(g2,g3);
              }
              
              if (g3 >= 0 && g1 >= 0) {
                  link(g3,g1);
              }
          }
       System.out.println(ret);
    }
    
    private static int root(int x) {
        if (x != pre[x]) pre[x] = root(pre[x]);
        return pre[x];
    }
    
    private static void link(int x,int y) {
        x = root(x);  y = root(y);
        if (x == y) return;
        ret--;
        if (rank[x] > rank[y]) pre[y] = x; else pre[x] = y;
        if (rank[x] == rank[y]) rank[y]++;
    }
    
    private static int gcd(int x,int y) {
        if (x == 0) return y;
        return gcd(y % x,x);
    }
}