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.*;
import java.util.*;

public class Solution {
	
	private BufferedReader in;
	private PrintWriter out;
	private StringTokenizer st;
	private int[] p;
	private int[] r;

	void solve() throws IOException {
		int n = nextInt();
		int[] a = new int[n];
		int[] b = new int[10000001];
		Arrays.fill(b, -1);
		for (int i = 0; i < n; ++i) {
			a[i] = nextInt();
			if (b[a[i]] != -1) {
				throw new AssertionError();
			}
			b[a[i]] = i;
		}
		int ans = n;
		p = new int[n];
		r = new int[n];
		for (int i = 0; i < n; ++i) {
			p[i] = i;
		}
		for (int p = 1; p * p <= 10000000; ++p) {
			for (int q = p + 1; Math.max(q * q - p * p, 2 * p * q) <= 10000000; q += 2) {
				if (gcd(p, q) != 1) {
					continue;
				}
				int u = q * q - p * p;
				int v = 2 * p * q;
				int w = p * p + q * q;
				if (u < b.length && v < b.length && b[u] != -1 && b[v] != -1 && get(b[u]) != get(b[v])) {
					unite(b[u], b[v]);
					ans--;
				}
				if (u < b.length && w < b.length && b[u] != -1 && b[w] != -1 && get(b[u]) != get(b[w])) {
					unite(b[u], b[w]);
					ans--;
				}
				if (v < b.length && w < b.length && b[v] != -1 && b[w] != -1 && get(b[v]) != get(b[w])) {
					unite(b[v], b[w]);
					ans--;
				}
			}
		}
		out.println(ans);
	}

	private int get(int i) {
		if (p[i] != i) {
			p[i] = get(p[i]);
		}
		return p[i];
	}
	
	void unite(int i, int j) {
		i = p[i];
		j = p[j];
		if (r[i] < r[j]) {
			p[i] = j;
		} else {
			p[j] = i;
		}
		if (r[i] == r[j]) {
			++r[i];
		}
	}

	private int gcd(int a, int b) {
		return b == 0 ? a : gcd(b, a % b);
	}

	Solution() throws IOException {
		in = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		
		eat("");
		
		solve();
		
		in.close();
		out.close();
	}
	
	private void eat(String str) {
		st = new StringTokenizer(str);
	}
	
	String next() throws IOException {
		while (!st.hasMoreTokens()) {
			String line = in.readLine();
			if (line == null) {
				return null;
			}
			eat(line);
		}
		return st.nextToken();
	}
	
	int nextInt() throws IOException {
		return Integer.parseInt(next());
	}
	
	long nextLong() throws IOException {
		return Long.parseLong(next());
	}
	
	double nextDouble() throws IOException {
		return Double.parseDouble(next());
	}

	public static void main(String[] args) throws IOException {
		new Solution();
	}
}