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:
import java.util.*;
import java.io.*;
import static java.lang.Math.*;
public class D2 {
    public static class DS {
        int[] parent;
        int[] rank;
        public DS(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i=0;i<n ;i++) {
                parent[i] = i;
            }
        }
        int find(int x) {
            if (parent[x]==x) {
                return x;
            } else {
                parent[x] = find(parent[x]);
                return parent[x];
            } 
        }
        void union(int x, int y){
            int xRoot = find(x);
            int yRoot = find(y);
            if (rank[xRoot]>rank[yRoot]) {
                parent[yRoot] = xRoot;
            } else if (xRoot!=yRoot) {
                parent[xRoot] = yRoot;
                if (rank[xRoot]==rank[yRoot]){
                    rank[yRoot]++;
                }
            }
        }
    }
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder buf = new StringBuilder();
    public static int gcd(int a, int b){
        return b==0?a:gcd(b, a%b);
    }

    public D2() throws Exception {
        int limit = 10000000;
        int xlimit = (int)sqrt(3*limit/2);
        int ylimit = (int)sqrt(limit/2);

        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        boolean[] set = new boolean[limit+1];
        for (int i=0;i<n ;i++) {
            int t = Integer.parseInt(st.nextToken());
            set[t] = true;
        }
        DS ds = new DS(limit+1);

        int ans = n;
        for (int x=1;x<=xlimit;x++) {
            int yl = min(x,ylimit+1);
            for (int y=1; y<yl; y++) {
                if((x&1)==(y&1))continue;
                if(gcd(x,y)!=1) continue;
                int x2 = x*x;
                int y2 = y*y;
                int c = x2+y2;
                int a = x2-y2;
                int b = 2*x*y;

                if(a>limit||b>limit)continue;

                if(set[a]&&set[b]) {
                    if(ds.find(a)!=ds.find(b)){
                        ds.union(a,b);
                        ans--;
                    }
                }

                if(c>limit) continue;

                if(set[a]&&set[c]) {
                    if(ds.find(a)!=ds.find(c)){
                        ds.union(a,c);
                        ans--;
                    }
                }

                if(set[c]&&set[b]) {
                    if(ds.find(c)!=ds.find(b)){
                        ds.union(c,b);
                        ans--;
                    }
                }


            }
        }
        buf.append(ans);
        System.out.print(buf);
    }

    public static void main(String[] args) throws Exception {
        new D2();
    }
}