#include<bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 const int N=1e5+;

 const int Pr=1e5;

 int K;

 bool vis[N];

 int tot=,pri[N]; LL mu[N];

 void prework() {

     vis[]=; mu[]=;

     for (int i=;i<=Pr;i++) {

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

         for (int j=;j<=tot&&i*pri[j]<=Pr;j++) {

             int k=i*pri[j]; vis[k]=;

             if (i%pri[j]==) {

                 mu[k]=; break;

             }

             mu[k]=-mu[i];

         }

     }

 }

 bool check(LL M) {

     LL i=,j,ret=;

     for (int i=;i*i<=M;i++) ret+=mu[i]*(M/(i*i));

     return ret>=K;

 }

 int main()

 {

     prework();

     int T; cin>>T;

     while (T--) {

         scanf("%d",&K);

         LL L=,R=*K;

         while (L<R) {

             LL M=(L+R)/;

             if (check(M)) R=M; else L=M+;

         }

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

     }

     return ;

 }