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.Scanner;
public class D_savior implements Runnable {
    int maxn=15000000;
    int inf =10000010;
    boolean []t=new boolean[maxn];
    boolean []used=new boolean[maxn];
    int []p=new int [maxn];
    int get(int x)
    {
        if(p[x]==-1)return x;
        else return p[x]=get(p[x]);
    }
    void unite(int i1, int j1)
    {
            int i = get(i1);
            int j = get(j1);
            if (i != j)
            {
                    if (i > j)
                            p[i] = j;
                    else
                            p[j] = i;
            }
    }
    void add_edge(int k1, int k2)
    {
            if (t[k1] && t[k2])
            {
                    if (k1 < inf && k2 < inf)
                            unite(k1,k2);
            }
    }
    int n;
    int gcd(int a, int b)
    {
            if (a == 0) return b;
            if (b == 0) return a;
            return gcd(b,a % b);
    }
    public static  void main(String[] args){
        new Thread(new D_savior()).start();
    }
    public void run(){
        try{
            Scanner cin= new Scanner (System.in);
            n=cin.nextInt();
            //for(int i=0;i<n;i++)t[i]=false;
            for(int i=0;i<n;i++)
            {
                int w=0;
                w=cin.nextInt();
                t[w]=true;
            }
            for(int i=0;i<maxn;i++)
            {
                p[i]=-1;
            }
            for(int i=1;i*i<maxn;i++)
            {
                for(int j=1;j<i&&(i*i+j*j)<maxn;j++)
                {
                    if(i%2==1&&j%2==1)continue;
                    if(i%2==0&&j%2==0)continue;
                    if(gcd(i,j)!=1)continue;
                    int k1=i*i-j*j;
                    int k2=2*i*j;
                    int k3=i*i+j*j;
                    add_edge(k1,k2);
                    add_edge(k2,k3);
                    add_edge(k1,k3);
                }
            }
            int ans=0;
            for(int i=0;i<maxn;i++)
            {
                if(p[i]==-1&&t[i])ans++;
            }
            System.out.println(ans);
        }catch(Exception e){
            e.printStackTrace();
        }
    }
}