#include<bits/stdc++.h>

 #define IOS ios::sync_with_stdio(false);//不可再使用scanf printf

 #define Max(a, b) ((a) > (b) ? (a) : (b))//禁用于函数，会超时

 #define Min(a, b) ((a) < (b) ? (a) : (b))

 #define Mem(a) memset(a, 0, sizeof(a))

 #define Dis(x, y, x1, y1) ((x - x1) * (x - x1) + (y - y1) * (y - y1))

 #define MID(l, r) ((l) + ((r) - (l)) / 2)

 #define lson ((o)<<1)

 #define rson ((o)<<1|1)

 #pragma comment(linker, "/STACK:102400000,102400000")//栈外挂

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}

     while (ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 typedef long long ll;

 const int maxn =  + ;

 const int maxm =  + ;

 const int MOD = ;//const引用更快，宏定义也更快

 const ll INF = ;

 const double eps = 1e-;

 bool not_prime[maxn];

 int prime[maxn];

 int Mob[maxn];

 void Mobius_sieve(int n)

 {

     int tot = ;

     not_prime[] = ;

     Mob[] = ;

     for(int i = ; i <= n; i++)

     {

         if(!not_prime[i])prime[tot++] = i, Mob[i] = - ;

         for(int j = ; j < tot && 1LL * prime[j] * i <= n; j++)

         {

             not_prime[prime[j] * i] = ;//每个合数x由它最小素因子prime[j]筛掉

             Mob[i * prime[j]] = (i % prime[j] ? -Mob[i]: );

             if(i % prime[j] == )break;//如果i % prime[j] == 0,不停止循环

             //那么接下来将用prime[j+1]筛去i*prime[j+1]，但实际上应该用prime[i]筛去,因为i%prime[j]==0

         }

     }

 }

 ll judge(ll m)

 {

     ll sum = ;

     for(ll i = ; i * i <= m; i++)

     {

         ll tmp = m / i / i;

         sum += Mob[i] * tmp;

     }

     return sum;

 }

 int main()

 {

     Mobius_sieve();

     int T;

     scanf("%d", &T);

     while(T--)

     {

         ll k;

         scanf("%lld", &k);

         ll l = , r = INF;

         ll ans;

         while(l <= r)

         {

             ll m = (l + r) / ;

             if(judge(m) >= k)ans = m, r = m - ;

             else l = m + ;

         }

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

     }

     return ;

 }