#include<bits/stdc++.h>
using namespace std;
int n,m,x,a[10000005];
int s[99990005],q[99990005];
void app(int y)
{
    for(int i=2;i*i<=1e1;i++)
    {
    	if(s[i]==0)
        {
        	for(int l=i;l*i<=1e1;l++)
        		s[i*l]=1;
        }
    }
}
int main()
{
	cin >> n;
	app(1);
	for(int i=0;i<n;i++)
	{
		int m,k;
		x=0;
		cin >> m;
		if(s[m]==0)
			cout << 0 << endl;
		else
		{
			k=m;
		    if(k%2==0)
		    {
		    	while(m%2==0)
		    		m=m/2;
		        x++;
		    }
			for(int l=3;l<=k/2&&m>1;l=l+2)
			{
				if(k%l==0&&s[l]==0)
				{
					while(m%l==0)
						m=m/l;
					x++;
				}
			}
			if(x==2)
				cout << 1 << endl;
			else
				cout << 0 << endl;
		}
	}
	return 0;
}