unordered_map<ll,ll>m;
rep(n,3,40){
	for(ll b=2,c;c=b**n,c<=1d12;++b){
		m[c]=n;
	}
}
ll@q;
rep(q){
	ll@c;
	auto i=m.find(c);
	if(i!=m.end()){
		wt(i->second);
	}else{
		wt(Isqrt_s(c)<0?1:2);
	}
}