（待写）

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
const int maxn=2e5+5;
bool Is_Primes[10005];
int Primes[10005];
int cnt;
void Prime(int n){
     cnt=0;
     memset(Is_Primes,0,sizeof(Is_Primes));
    for(int i=2;i<=n;i++){
        if(!Is_Primes[i])
            Primes[cnt++]=i;
        for(int j=0;j<cnt&&i*Primes[j]<n;j++){
            Is_Primes[Primes[j]*i]=1;
            if(i%Primes[j]==0)break;
        }
    }
}
int main(){
	Prime(10001);
	int t;
	scanf("%d",&t);
	while(t--){
		long long n;
		scanf("%lld",&n);
		int ans=500;
		for(int i=0;i<cnt;i++){
			int flag=0;
			while(n%Primes[i]==0){
				n/=Primes[i];
				flag++;
			}
			if(flag)
			ans=min(flag,ans);
		}
		if(n==1)printf("%d
",ans);
		else {
			ll a=powl(n,1.0/4);
			ll b=powl(n,1.0/3);
			ll c=sqrt(n);
			if(powl(a,4)==n||powl(a-1,4)==n||powl(a+1,4)==n)printf("%d
",min(ans,4));//不这样搞会有精度问题
			else  if(powl(b,3)==n||powl(b-1,3)==n||powl(b+1,3)==n)printf("%d
",min(ans,3));
			else if(c*c==n)printf("%d
",min(ans,2));
			else printf("1
");
		}
	}
	return 0;
}