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 f {
public static void main(String[] args) throws IOException {
	input.init(System.in);
	int sz = input.nextInt();
	DisjointSet ds = new DisjointSet(sz);
	PrintWriter out = new PrintWriter(System.out);
	int[] rev = new int[10000001];
	Arrays.fill(rev, -1);
	for(int i = 0; i<sz; i++) rev[input.nextInt()] = i;
	res = sz;
	for(int n = 1; n*n <= 10_000_000; n++)
		for(int m = n+1; m*n <= 10_000_000; m+=2)
		{
			int a = m*m - n*n, b = 2*m*n, c = m*m + n*n;
			if(a > 10_000_000 || b > 10_000_000) break;
			if(gcd(n, m) != 1) continue;
			if(rev[a] != -1 && rev[b] != -1)
			{
				ds.union(rev[a], rev[b]);
			}
			if(c < rev.length && rev[c] != -1)
			{
				if(rev[a] != -1) ds.union(rev[a], rev[c]);
				if(rev[b] != -1) ds.union(rev[b], rev[c]);
			}
		}
	out.println(res);
	out.close();
}
static int res;
public static class DisjointSet
{
	int[] map; //negative if root, more negative means bigger set; if nonnegative, then it indicates the parent 
	public DisjointSet(int n)
	{
		map = new int[n+1];
		Arrays.fill(map, -1);
	}
	public int find(int x)
	{
		if(map[x] < 0) return x;
	    return map[x] = find(map[x]);
	}
	public void union(int a, int b)
	{
		int roota = find(a), rootb = find(b);
		if(roota == rootb)
			return;
		res--;
		if(map[roota] < map[rootb])
		{
			map[roota] += map[rootb]; //add the sizes
			map[rootb] = roota; //connect the smaller to the bigger
		}
		else
		{
			map[rootb] += map[roota];
			map[roota] = rootb;
		}
	}
}
static long key(long a, long b)
{
	return a * 10_000_001 + b;
}
static int gcd(int a, int b)
{
	return b == 0 ? a : gcd(b, a%b);
}
public static class input {
	static BufferedReader reader;
	static StringTokenizer tokenizer;

	static void init(InputStream input) {
		reader = new BufferedReader(new InputStreamReader(input));
		tokenizer = new StringTokenizer("");
	}

	static String next() throws IOException {
		while (!tokenizer.hasMoreTokens())
			tokenizer = new StringTokenizer(reader.readLine());
		return tokenizer.nextToken();
	}

	static int nextInt() throws IOException {
		return Integer.parseInt(next());
	}

	static double nextDouble() throws IOException {
		return Double.parseDouble(next());
	}

	static long nextLong() throws IOException {
		return Long.parseLong(next());
	}
}
}