// Include
#include <fstream>
#include <utility>
#include <cmath>
#include <vector>
using namespace std;

// Definitii
#define ll long long
#define pb push_back
#define mp make_pair

// Constante
const int sz = (int)(1e6)+1;
const int mod = 4783;

// Functii
void hashInsert(ll val, int id);
int hashCheck(ll val);
bool isPrime(int val);

// Variabile
ifstream in("ubercool.in");
ofstream out("ubercool.out");

int tests;
ll number;

bool notPrime[sz];
bool answer[sz];

vector<pair<ll, int> > hash[mod];

// Main
int main()
{
	in >> tests;
	for(int i=1 ; i<=tests ; ++i)
	{
		in >> number;
		hashInsert(number, i);
	}
	
	for(int i=2 ; i<=sz ; ++i)
	{
		if(!notPrime[i])
		{
			for(ll j=i*i*i ; j>0 ; j*=i)
				answer[hashCheck(j)] = true;
			
			for(int j=i*2 ; j<=sz ; j+=i)
				notPrime[j] = true;
		}
	}
	
	for(int i=0 ; i<mod ; ++i)
	{
		vector<pair<ll, int> >::iterator it, end = hash[i].end();
		for(it=hash[i].begin() ; it!=end ; ++it)
		{
			long double dRoot = sqrt((long double)(it->first));
			long double  roundRoot = round(dRoot);
			if(dRoot == roundRoot)
				if(isPrime((int)(roundRoot)))
					answer[it->second] = true;
		}
	}
	
	for(int i=1 ; i<=tests ; ++i)
		out << (answer[i]? "DA" : "NU") << '\n';
	
	in.close();
	out.close();
	return 0;
}

void hashInsert(ll val, int id)
{
	int pos = (int)(val % (ll)mod);
	hash[pos].pb(mp(val, id));
}

int hashCheck(ll val)
{
	int pos = (int)(val % (ll)mod);
	vector<pair<ll, int> >::iterator it, end = hash[pos].end();
	
	for(it=hash[pos].begin() ; it!=end ; ++it)
		if(it->first == val)
		{
			int ret = it->second;
			hash[pos].erase(it);
			return ret;
		}
	
	return 0;
}

bool isPrime(int val)
{
	int limit = (int)round(sqrt(val));
	
	for(int i=2 ; i<=limit ; ++i)
		if(!(val%i))
			return false;
	
	return true;
}