#include <cstdio>

#include <algorithm>

#include <cmath>

#include <cstring>

#define setIO(s) freopen(s".in","r",stdin)

#define maxn 50080

const long long inf = 1844387848;

#define ll long long

using namespace std;

int mu[maxn],vis[maxn],prime[maxn],tot;

int main(){

    //setIO("input");

    mu[1]=1;

    for(int i=2;i<maxn;++i) {

        if(!vis[i]) prime[++tot]=i,mu[i]=-1;

            for(int j=1;j<=tot&&(ll)prime[j]*i < (ll) maxn; ++j) {

                vis[prime[j]*i] = 1;

                if(i % prime[j]==0) { mu[prime[j]*i] = 0; break;  }

                mu[prime[j]*i] = -mu[i];

            }

    }

    int T;

    long long k;

    long long l,r,ans;

    scanf("%d",&T);

    while(T--){

        scanf("%lld",&k);

        l=1,r=inf,ans=0;

        while(l <= r) {

            long long mid=(l+r)>>1;

            long long tmp=0;

            for(ll i=1;i*i<=mid;++i)

                tmp+=mu[i]*(mid/(i*i)) ;

            if(tmp>=k) r = mid-1,ans=mid;

            else l = mid + 1;

        }

        printf("%lld\n",ans);

    }

    return 0;

}