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 static java.util.Arrays.deepToString;

import java.io.*;
import java.util.*;

public class Savior {

//  static final String F_IN            = "inout/cf/beta56/savior_big.in";
//  static final File F_OUT             = new File("inout/cf/beta56/savior.out");
    static final InputStream F_IN       = System.in;
    static final PrintStream F_OUT      = System.out;
    
    static final int MAX_V              = 10000000+5;
    
    int n, ans;
    int[] a;
    int[] f;
    
    void readInput() throws Exception {
//      BufferedReader br = new BufferedReader(new FileReader(F_IN));
        BufferedReader br = new BufferedReader(new InputStreamReader(F_IN));
        n = Integer.parseInt(br.readLine());
        a = toInts(br.readLine());
    }
    
    void writeOutput() throws Exception {
        PrintWriter out = new PrintWriter(F_OUT);
        out.println(ans);
        out.close();
    }
    
    long gcd(long x, long y) {
        while (x>0&&y>0) {
            if (x>y) x%=y; else y%=x;
        }
        return x^y;
    }

    int root(int x) {
        while (f[x]!=-1) x = f[x];
        return x;
    }

    void adjust(int x, int rx) {
        int i = x;
        while (f[i]!=-1) {
            int j = f[i]; 
            f[i] = rx;
            i = j;
        }       
    }
    
    void add(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        if (rx!=ry) f[ry] = rx;
        adjust(x, rx);
        adjust(y, rx);
    }
    
    void consider(long x, long y) {
        int xx = (int) x, yy = (int) y;
        if (f[xx]!=-2 && f[yy]!=-2) add(xx, yy);
    }
    
    void solveProblem() {
        f = new int[MAX_V];
        Arrays.fill(f, -2);
        
        int maxValue = 0;
        for (int e: a) {
            f[e] = -1;
            maxValue = Math.max(maxValue, e);
        }
        maxValue+=5;
        
        for (long i=1; i<=maxValue; i++)
            for (long j=1; j<=i; j++) {
                long x = 2*i*j, y = i*i-j*j, z = i*i+j*j;
                if (((i&1)^(j&1))==1) {
                    int c = 0;
                    if (x<maxValue && f[(int) x]!=-2) c++;
                    if (y<maxValue && f[(int) y]!=-2) c++;
                    if (z<maxValue && f[(int) z]!=-2) c++;
                    if (c>=2 && gcd(x, y)!=1) continue;
                    if (x<maxValue && y<maxValue) consider(x, y);
                    if (y<maxValue && z<maxValue) consider(y, z);
                    if (z<maxValue && x<maxValue) consider(z, x);
                }
                if (x>=maxValue&&z>=maxValue) break;
            }
        
        ans = 0;
        for (int i=1; i<MAX_V; i++)
            if (f[i]==-1) ans++;
    }
    
    public Savior() throws Exception {
        readInput();
        solveProblem();
        writeOutput();
    }
    
    public static void main(String[] args) throws Exception {
        new Savior();
    }
    
    void debug(Object... os) {
        System.out.println(deepToString(os));
    }

    String[] toTokens(String s) {
        StringTokenizer st = new StringTokenizer(s);
        List<String> list = new ArrayList<String>();
        while (st.hasMoreTokens()) {
            list.add(st.nextToken());
        }
        String[] res = new String[list.size()];
        for (int i=0; i<res.length; i++) res[i] = list.get(i);
        return res;
    }
    
    int[] toInts(String s) {
        StringTokenizer st = new StringTokenizer(s);
        List<Integer> list = new ArrayList<Integer>();
        while (st.hasMoreTokens()) {
            list.add(Integer.parseInt(st.nextToken()));
        }
        int[] res = new int[list.size()];
        for (int i=0; i<res.length; i++) res[i] = list.get(i);
        return res;
    }
    
    long[] toLongs(String s) {
        StringTokenizer st = new StringTokenizer(s);
        List<Long> list = new ArrayList<Long>();
        while (st.hasMoreTokens()) {
            list.add(Long.parseLong(st.nextToken()));
        }
        long[] res = new long[list.size()];
        for (int i=0; i<res.length; i++) res[i] = list.get(i);
        return res;
    }
    
}