ll@T,L=1d12,t;set<ll>S[40];rep(e,2,40)rep(i,L){if(((t=i)**=e)<=L)S[e].insert(t);else break;}rep(T){ll@N;wt(max[e,1,40@e^1?S[e].count(N):1](e));}