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;
import static java.lang.Math.*;

public class Main 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 void debug(String s) {
		System.out.println(s);
	}

	public static void main(String[] args) {
		new Thread(new Main()).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());
	}
}