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.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;

public class Main {
	public static int g[];
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int a[] = new int[n];
        int MAX = 10000001;
        int idx[] = new int[MAX];

        g = new int[n];
        for(int i = 0; i < MAX; i++) idx[i] = -1;
        for(int i = 0; i < n; i++){
        	a[i] = scan.nextInt();
        	idx[a[i]] = i;
        	g[i] = i;
        }
        
        for(long y = 1; y * y < MAX; y++){
        	for(long x = y + 1; x * y < MAX; x+= 2){
        		long p = x * x - y * y;
        		long q = 2 * x * y;
        		long r = x * x + y * y;
        		
        		if(p > MAX || q > MAX) break;
        		
        		//System.out.println(x + " / " + y + " // " + p + "," + q + "," + r);
        		int pidx = idx[(int)p];
        		int qidx = idx[(int)q];
        		
        		if(pidx > -1 && qidx > -1){
        			if(gcd(p,q) == 1){
            			int proot = findRoot(pidx);
            			int qroot = findRoot(qidx);
            			
            			g[qroot] = proot;	
        			}
        		}
        		if(r < MAX){
            		int ridx = idx[(int)r];
            		if(pidx > -1 && ridx > -1){
            			if(gcd(p, r) == 1){
                			int proot = findRoot(pidx);
                			int rroot = findRoot(ridx);
                			g[rroot] = proot;
            			}
            		}
            		if(qidx > -1 && ridx > -1){
            			if(gcd(q,r) == 1){

                			int qroot = findRoot(qidx);
                			int rroot = findRoot(ridx);
                			g[rroot] = qroot;	
            			}
            		}
        		}
        	}
        }
        Set<Integer> s = new HashSet<Integer>();
        for(int i = 0; i < n; i++){
        	//System.out.println(i + " : " + g[i]);
        	s.add(findRoot(g[i]));
        }
        System.out.println(s.size());
    }
	public static int findRoot(int idx){
		if(g[idx] == idx) return idx;
		else return findRoot(g[idx]);
	}
	
	public static long gcd(long a, long b){
		if(a < b) return gcd(b, a);
		if(b == 0) return a;
		return gcd(b, a % b);
	}
}