#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;

int n;
int a[11451];

bool Isprime(int n){
	if(n < 2) return false;
	else if(n == 2) return true;
	for(int i = 2;i * i<= n;i++){
		if(n % i == 0){
			return false;
		}
	}
	return true;
}

signed main(){
	scanf("%d",&n);
	for(int i = 1;i <= n;i++){
		int x;
		int tot = 0;
		scanf("%d",&x);
		if(Isprime(x) == true){
			cout<<0<<endl;
		}else {
			for(int j = 2;j <= x;j++){
				if(Isprime(j) == true){
					while(x % j == 0){
						x /= j;
					}
					tot++;
					cout<<j<<endl;
				}
				
			}
			if(tot > 2){
				cout<<0<<endl;
			}else{
				cout<<1<<endl;
			}
		}
	}
	return 0;
}