#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cmath>
#include<algorithm>
#define FILE "read"
using namespace std;
typedef long long ll;
const int MAXN=(int)1e5,D=50;
const ll INF=(ll)1e10;
int CASE,cnt,prime[MAXN+D],check[MAXN+D],mu[MAXN+D];
namespace INIT{
	char buf[1<<15],*fs,*ft;
	inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
	inline ll read(){
		ll x=0,f=1;  char ch=getchar();
		while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
		while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
		return x*f;
	}
}using namespace INIT;
void pre(){
	mu[1]=1;
	for(int i=2;i<=MAXN;++i){
		if(!check[i])  prime[++cnt]=i,mu[i]=-1;
		for(int j=1;j<=cnt&&i*prime[j]<=MAXN;++j){
			check[i*prime[j]]=1;
			if(i%prime[j]==0)  {mu[i*prime[j]]=0;break;}
			mu[i*prime[j]]=-mu[i];
		}
	}
}
ll solve(ll x){
	ll temp=(ll)sqrt(x*1.0),sum(0);
	for(int i=1;i<=temp;++i){
		sum+=mu[i]*(x/((ll)i*i));
	}
	return sum;
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	CASE=read();  pre();
	while(CASE--){
		ll k=read(),l(0),r(INF),ans(0);
		while(l<=r){
			ll mid=(l+r)>>1;
			if(solve(mid)>=k)  {ans=mid;  r=mid-1;}
			else l=mid+1;
		}
		printf("%lld\n",ans);
	}
	return 0;
}