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.IOException;
import java.util.Arrays;
import java.io.FilterInputStream;
import java.util.HashMap;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.TreeSet;
import java.io.BufferedInputStream;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Zyflair Griffane
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputUtil in = new InputUtil(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		Task solver = new Task();
		solver.solve(1, in, out);
		out.close();
	}
}

class Task {

    final int MAX = 10_000_000;

    // The main solution method
    public void solve(int testNumber, InputUtil in, PrintWriter out) {
        int n = in.nextInt();
        int[] arr = in.nextIntArray(n);

        boolean[] set = new boolean[MAX + 1];
        for (int i : arr) set[i]= true;

        DisjointSet ds = unionTriplets(IntArrayUtil.max(arr), set);
        int res = 0;
        for (int i: arr) {
            if (set[ds.find(i)]) {
                set[ds.find(i)] = false;
                res++;
            }
        }
        out.println(res);
    }
    public DisjointSet unionTriplets(int max, boolean[] set) {
        DisjointSet ds = new DisjointSet(max + 1);
        long yMax = (long) Math.sqrt(max / 2.0);
        for (long y = 1; y <= yMax; y++) {
            for (long x = y + 1; (x * y << 1) <= max || (x * x + y * y) <= max; x += 2) {
                long u = x * x - y * y;
                long v = x * y << 1;
                long w = x * x + y * y;
                if (gcd(x, y) > 1) {
                    continue;
                }
//                System.out.println("BWAH " + u + " " + v + " " + w + " " + set + " " + max);
                if (v <= max && set[(int) v]) {
//                    System.out.println("AND... ");
                    if (u <= max && set[(int) u]) {
//                        System.out.print("YES!");
                        ds.union((int) u, (int) v);
                    }
                    if (w <= max && set[(int) w]) {
                        ds.union((int) v, (int) w);
                    }
                }
                if (u <= max && w <= max && set[(int) w] && set[(int) u]) {
                    ds.union((int) u, (int) w);
                }
            }
        }
        return ds;
    }

    public long gcd(long x, long y) {
        return y == 0 ? x : gcd(y, x % y);
    }
}

class InputUtil {

    JoltyScanner in;

    public InputUtil(InputStream istream) {
        in = new JoltyScanner(istream);
    }

    public String next() {
        return in.next();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public int[] nextIntArray (int size) {
        int[] arr = new int[size];
        for (int i = 0; i < size; i++) {
            arr[i] = in.nextInt();
        }
        return arr;
    }

}

class DisjointSet {
    public int[] par;
    public int[] rank;
//    public int[] size;
    public int sets;

    public DisjointSet(int n) {
        sets = n;
        par = new int[n];
        rank = new int[n];
//        size = new int[n];
//        Arrays.fill(size, 1);
        for (int i = 0; i < n; i++) {
            par[i] = i;
        }
    }

    public void union(int u, int v) {
        if (find(u) == find(v)) return;
        sets --;
        if (rank[find(u)] < rank[find(v)]) {
            int t = u;
            u = v;
            v = t;
        }
//        size[find(u)] += size[find(v)];
//        size[find(v)] = 0;
        par[find(v)] = find(u);
        rank[find(u)] = Math.max(rank[find(u)], rank[find(v)] + 1);
    }

//    public int size(int u) {
//        return size[find(u)];
//    }

    public int find(int u) {
        if (par[u] == u) {
            return u;
        }
        else {
            par[u] = find(par[u]);
            return par[u];
        }
    }
}

class IntArrayUtil {

    public static int max(int[] arr) {
        if (arr.length == 0) {
            throw new RuntimeException("Passed in array has length of 0");
        }
        int max = arr[0];
        for (int a: arr) {
            if (a > max) {
                max = a;
            }
        }
        return max;
    }

}

class JoltyScanner {
    public static final int BUFFER_SIZE = 1 << 16;
	public static final char NULL_CHAR = (char) -1;

	StringBuilder str = new StringBuilder();
	byte[] buffer = new byte[BUFFER_SIZE];
	boolean EOF_FLAG = false;
	int bufferIdx = 0, size = 0;
	char c = NULL_CHAR;
	BufferedInputStream in;

	public JoltyScanner(InputStream in) {
		this.in = new BufferedInputStream(in, BUFFER_SIZE);
	}

	public int nextInt() {
		long x = nextLong();
		if (x > Integer.MAX_VALUE || x < Integer.MIN_VALUE) {
			throw new ArithmeticException("Scanned value overflows integer");
		}
		return (int) x;
	}

	public long nextLong() {
		boolean negative = false;
		if (c == NULL_CHAR) {
			c = nextChar();
		}
		for (; !EOF_FLAG && (c < '0' || c > '9'); c = nextChar()) {
			if (c == '-') {
				negative = true;
			}				
		}
		checkEOF();
		long res = 0;
		for (; c >= '0' && c <= '9'; c = nextChar()) {
			res = (res << 3) + (res << 1) + c - '0';
		}
		return negative ? -res : res;
	}

    public String next() {
		checkEOF();
		if (c == NULL_CHAR) {
			c = nextChar();
		}
		while (Character.isWhitespace(c)) {
			c = nextChar();
			checkEOF();
		}
		str.setLength(0);
		for (; !EOF_FLAG && !Character.isWhitespace(c); c = nextChar()) {
			str.append(c);
		}
		return str.toString();
	}

    public char nextChar() {
		if (EOF_FLAG) {
			return NULL_CHAR;
		}
		while (bufferIdx == size) {
			try {
				size = in.read(buffer);
				if (size == -1) {
					throw new Exception();
				}
			} catch (Exception e) {
				EOF_FLAG = true;
				return NULL_CHAR;
			}
			if (size == -1) {
				size = BUFFER_SIZE;
			}
			bufferIdx = 0;
		}
		return (char) buffer[bufferIdx++];
	}

    public void checkEOF() {
		if (EOF_FLAG) {
			throw new EndOfFileException();
		}
	}

	public class EndOfFileException extends RuntimeException {
	}
}