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.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class D implements Runnable {
	int[] f, r;

	private void solve() throws Exception {
		final int N = 10000001;
		int n = in.nextInt(), mxv = 0;
		boolean[] use = new boolean[N];
		f = new int[N]; r = new int[N];
		
		for (int i = 1; i <= n; ++i) {
			int x = in.nextInt();
			mxv = Math.max(mxv, x);
			use[x] = true;
			f[x] = x;
		}
		
		for (int p = 1; p <= mxv; ++p)
			for (int q = p+1; q <= mxv; ++q) {
				if ((long)p*q*2 > mxv) break;
				int x = p*q*2;
				if ((long)q*q-p*p > mxv) break;
				int y = q*q-p*p;
				if (gcd(x, y) > 1) continue;
				if (use[x] && use[y])
					merge(x, y);
				
				if ((long)q*q+p*p > mxv) continue;
				int z = q*q+p*p;
				if (gcd(x, z) > 1 || gcd(y, z) > 1)
					continue;
				if (use[z] && use[x]) merge(z, x);
				if (use[z] && use[y]) merge(z, y);
			}
		
		int ans = 0;
		for (int i = 1; i < N; ++i)
			ans += i == f[i] ? 1 : 0;
		out.println(ans);
	}
	
	long gcd(long a, long b) {
		return b == 0 ? a : gcd(b, a % b);
	}
	
	private int getf(int x) {
		if (x == f[x]) return x;
		int r = getf(f[x]);
		f[x] = r;
		return r;
	}
	
	private void merge(int x, int y) {
		x = getf(x);
		y = getf(y);
		if (x == y) return;
		if (r[x] < r[y])
			f[x] = y;
		else {
			f[y] = x;
			if (r[x] == r[y]) ++r[x];
		}
	}

	public static void main(String args[]) {
		new D().run();
	}

	InputReader in;

	PrintWriter out;

	public void run() {
		try {
			in = new InputReader(System.in);
			out = new PrintWriter(System.out);
			solve();
			in.close();
			out.close();
		} catch (Exception e) {
			e.printStackTrace();
			System.exit(1);
		}
	}

	static class InputReader {
		BufferedReader reader;

		StringTokenizer tokenizer;

		InputReader(InputStream in) throws IOException {
			reader = new BufferedReader(new InputStreamReader(in));
			tokenizer = null;
		}

		void close() throws IOException {
			reader.close();
		}

		String next() throws IOException {
			while (null == tokenizer || !tokenizer.hasMoreTokens())
				tokenizer = new StringTokenizer(reader.readLine());
			return tokenizer.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());
		}

	}

}