#include <iostream>
#include <cmath>

using namespace std;

bool isPrime(int a)
{
	if(a == 2 || a == 3 || a == 5)
	{
		return true;
	}
	if(a == 1)
	{
		return false;
	}
	if(a%2)
	{
		if(a%3)
		{
			if(a%5)
			{
				for(int i = 2; i < (sqrt(a)+1); i++)
				{
					if(!(a%i))
					{
						return false;
					}
				}
				return true;
			}
		}
	}
	return false;
}


int main()
{
	int a,b;
	cin >> a;
	for(int i = 0; i < a; i++)
	{
		cin >> b;
		if(isPrime(b))
		{
			cout << b << " is prime" << endl;
		}
		else
		{
			cout << b << " is not prime" << endl;
		}
	}
	return 0;
}