组合枚举n/i/i，贡献为miu倍
/*H E A D*/
int mu[maxn],prime[maxn],cnt;
bool isprime[maxn];
void sai(int n){
mu[0]=0;mu[1]=1;
rep(i,2,n) isprime[i]=1;
rep(i,2,n){
if(isprime[i]){
prime[++cnt]=i;
mu[i]=-1;
}
rep(j,1,cnt){
if(i*prime[j]>n) break;
isprime[i*prime[j]]=0;
if(i%prime[j]==0){
mu[i*prime[j]]=0;
break;
}
mu[i*prime[j]]=-mu[i];
}
}
}
ll C(ll x){
ll rt=sqrt(x+0.5),ans=0;
rep(i,1,rt){
ans+=x/i/i*mu[i];
}
return ans;
}
int main(){
sai((int)1e6-11);
int T=read();
while(T--){
ll x=read();
ll l=x,r=2e9+50,mid,ans;
while(r>=l){
mid=l+r>>1;
if(C(mid)>=x){
r=mid-1;
ans=mid;
}
else{
l=mid+1;
}
}
println(ans);
}
return 0;
}