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 java.math.BigInteger;
public class D_savior implements Runnable {
        StringTokenizer tokenizer = new StringTokenizer("");
        BufferedReader in;
        PrintStream out;
        int M = 10000000 + 5;
        boolean [] have = new boolean[M];
        int [] p = new int[M];
        int ans;
        Random rand = new Random();
        public static void main(String[] args) {
                new Thread(new D_savior()).start();
        }            
        int par(int x) {
                return x == p[x] ? x : (p[x] = par(p[x]));
        }
        void unite(int x, int y) {
                x = par(x);
                y = par(y);
                if (x == y) return;
                ans--;
                if (rand.nextBoolean()) p[x] = y; else p[y] = x;
        }
        int gcd(int a, int b) {
                return a == 0 ? b : gcd(b % a, a);
        }
        public void run() {
                //try {
                        Locale.setDefault(Locale.US);
                        in = new BufferedReader(new InputStreamReader(System.in));
                        out = new PrintStream(System.out);

                        int n = nextInt();
                        for (int i = 0; i < n; i++) have[nextInt()] = true;
                        for (int i = 1; i < M; i++) p[i] = i;
                        ans = n;

                        outer:
                        for (int v = 1; v * v <= M; v++) {
                                boolean bz = true, bx = true, by = true;
                                for (int u = v + 1; ; u++) {
                                        if (gcd(u, v) != 1 || (u % 2 == 1 && v % 2 == 1)) continue;
                                        int z = u * u + v * v, x = u * u - v * v, y = 2 * u * v;
                                        if (z >= M) bz = false;
                                        if (y >= M) by = false;
                                        if (x >= M) bx = false;
                                        if (!bz && (!bx || !by)) continue outer;
                                        if (bz && have[x] && have[z]) unite(x, z);
                                        if (by && bz && have[y] && have[z]) unite(y, z);
                                        if (by && have[x] && have[y]) unite(x, y);
                                }
                        }
                        out.println(ans);
                //} catch (Exception e) {
                       // e.printStackTrace();
                //}
        }

        boolean seekForToken() {
                while (!tokenizer.hasMoreTokens()) {
                        String s = null;
                        try {
                                s = in.readLine();
                        } catch (Exception e) {
                                e.printStackTrace();
                        }
                        if (s == null)
                                return false;
                        tokenizer = new StringTokenizer(s);
                }
                return true;
        }
///////////////////////////////////////////////////////////////////////////////////////
        String nextToken() {
                return seekForToken() ? tokenizer.nextToken() : null;
        }

        int nextInt() {
                return Integer.parseInt(nextToken());
        }

        long nextLong() {
                return Long.parseLong(nextToken());
        }

        double nextDouble() {
                return Double.parseDouble(nextToken());
        }

        BigInteger nextBig() {
                return new BigInteger(nextToken());
        }
}