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.math.*;
import static java.lang.Character.isDigit;
import static java.lang.Character.isLowerCase;
import static java.lang.Character.isUpperCase;
import static java.lang.Math.*;
import static java.math.BigInteger.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;
import static java.lang.Character.isDigit;

public class Main{
    static void debug(Object...os){
        System.err.println(deepToString(os));
    }
    
    void run(){
        int n=nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++)a[i]=nextInt();
        System.out.println(calc(a));
    }
    
    class UnionFind{
        final int[] tree;
        
        public UnionFind(int n){
            this.tree=new int[n];
            fill(tree,-1);
        }
        void union(int x,int y){
            x=root(x);
            y=root(y);
            if(x!=y){
                if(tree[x]<tree[y]){
                    int t=x;
                    x=y;
                    y=t;
                }
                tree[x]+=tree[y];
                tree[y]=x;
            }
        }
        
        boolean find(int x,int y){
            return root(x)==root(y);
        }
        
        int root(int x){
            return tree[x]<0?x:(tree[x]=root(tree[x]));
        }
        
        int size(int x){
            return -tree[root(x)];
        }
    }
    
    private int calc(int[] as){
        int N=as.length;
        boolean[] bs=new boolean[10000001];
        int[] rev=new int[10000001];
        for(int i=0;i<N;i++) {
            bs[as[i]]=true;
            rev[as[i]]=i;
        }
        UnionFind uf = new UnionFind(N);
        int cnt=0;
        for(int n=1;2*n*n<=10000000;n++) {
            for(int m=n+1;max(m*m-n*n,2*m*n)<=10000000;m++) {
                if((n&1)!=(m&1) && gcd(n,m)==1) {
                    cnt++;
                    int x=m*m-n*n,y=2*m*n,z=m*m+n*n;
                    if(x<bs.length && y<bs.length && bs[x] && bs[y])uf.union(rev[x],rev[y]);
                    if(x<bs.length && z<bs.length && bs[x] && bs[z])uf.union(rev[x],rev[z]);
                    if(z<bs.length && y<bs.length && bs[z] && bs[y])uf.union(rev[z],rev[y]);
                }
            }
        }
        int res=0;
        for(int i=0;i<N;i++)if(uf.tree[i]<0)res++;
        return res;
    }
    long gcd(long x,long y){
        return x==0?y:gcd(y%x,x);
    }

    int nextInt(){
        try{
            int c=System.in.read();
            if(c==-1) return c;
            while(c!='-'&&(c<'0'||'9'<c)){
                c=System.in.read();
                if(c==-1) return c;
            }
            if(c=='-') return -nextInt();
            int res=0;
            do{
                res*=10;
                res+=c-'0';
                c=System.in.read();
            }while('0'<=c&&c<='9');
            return res;
        }catch(Exception e){
            return -1;
        }
    }
    
    long nextLong(){
        try{
            int c=System.in.read();
            if(c==-1) return -1;
            while(c!='-'&&(c<'0'||'9'<c)){
                c=System.in.read();
                if(c==-1) return -1;
            }
            if(c=='-') return -nextLong();
            long res=0;
            do{
                res*=10;
                res+=c-'0';
                c=System.in.read();
            }while('0'<=c&&c<='9');
            return res;
        }catch(Exception e){
            return -1;
        }
    }
    
    double nextDouble(){
        return Double.parseDouble(next());
    }
    
    String next(){
        try{
            StringBuilder res=new StringBuilder("");
            int c=System.in.read();
            while(Character.isWhitespace(c))
                c=System.in.read();
            do{
                res.append((char)c);
            }while(!Character.isWhitespace(c=System.in.read()));
            return res.toString();
        }catch(Exception e){
            return null;
        }
    }
    
    String nextLine(){
        try{
            StringBuilder res=new StringBuilder("");
            int c=System.in.read();
            while(c=='\r'||c=='\n')
                c=System.in.read();
            do{
                res.append((char)c);
                c=System.in.read();
            }while(c!='\r'&&c!='\n');
            return res.toString();
        }catch(Exception e){
            return null;
        }
    }
    public static void main(String[] args){
        new Main().run();
    }
}