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.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;

public class D {

    static StreamTokenizer st;
    static int[]p, rank;
    static boolean[]used;
    static int max = (int) 1e7;
    public static void main(String[] args) throws IOException{
        st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        int n = nextInt();
        int[]a = new int[n+1];
        used = new boolean[max+1];
        for (int i = 1; i <= n; i++) {
            a[i] = nextInt();
            used[a[i]] = true;
        }
        p = new int[max+1];
        rank = new int[max+1];
        for (int i = 1; i <= n; i++) {
            p[a[i]] = a[i];
            rank[a[i]] = 1;
        }
        for (int y = 1; y*y <= max; y++) {
            for (int x = y+1; 2*x*y <= max && x*x-y*y <= max; x++) {
                if (gcd(x*x-y*y, 2*x*y) != 1 || gcd(x*x-y*y, x*x+y*y) != 1 || gcd(2*x*y, x*x+y*y) != 1)
                    continue;
                unite(x*x-y*y, 2*x*y);
                unite(x*x-y*y, x*x+y*y);
                unite(2*x*y, x*x+y*y);
            }
        }
        Arrays.fill(used, false);
        for (int i = 1; i <= n; i++) {
            used[get_fath(a[i])] = true;
        }
        int ans = 0;
        for (int i = 1; i <= max; i++) {
            if (used[i])
                ans++;
        }
        pw.print(ans);
        pw.close();
    }

    private static void unite(int v1, int v2) {
        if (v1 > max || v2 > max || !used[v1] || !used[v2])
            return;
        int p1 = get_fath(v1);
        int p2 = get_fath(v2);
        if (p1 != p2) {
            if (rank[p1] < rank[p2]) {
                int t = p1;
                p1 = p2;
                p2 = t;
            }
            p[p2] = p1;
            rank[p1] += rank[p2];
        }
    }

    private static int gcd(int a, int b) {
        if (b==0)
            return a;
        return gcd(b, a % b);
    }

    private static int get_fath(int v) {
        if (p[v]==v)
            return v;
        return p[v] = get_fath(p[v]);
    }

    private static int nextInt() throws IOException{
        st.nextToken();
        return (int) st.nval;
    }

}