考虑二分，然后变成判断 $\le x$ 的无平方因子数的个数。

我们考虑一个有问题的做法，枚举质数 $p$ ，将 $p^2$ 的倍数全部去掉。不难发现，这样有些数字被去了很多遍。能不能容斥呢？我们考虑枚举无平方因子数 $t$ ，将 $t^2$ 的倍数全部去掉 / 加回来就好了。系数是 $(-1)^c$ 其中 $c$ 为质因数个数。然后可以发现，这个系数就是 $\mu$ 。。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 1000006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , m;

int mu[MAXN] , pri[MAXN] , en;
void sieve( ) {
    mu[1] = 1;
    for( int i = 2 ; i < MAXN ; ++ i ) {
        if( !pri[i] ) pri[++ en] = i , mu[i] = -1;
        for( int j = 1 ; j <= en && pri[j] * i < MAXN ; ++ j ) {
            pri[i * pri[j]] = 1;
            if( i % pri[j] == 0 ) {
                mu[i * pri[j]] = 0; break;
            }
            mu[i * pri[j]] = -mu[i];
        }
    }
}

bool chk( ll x ) {
    ll re = 0;
    for( ll i = 1 ; i * i <= x ; ++ i ) if( mu[i] )
        re += x / ( i * i ) * mu[i];
    return re < n;
}

void solve() {
    cin >> n;
    ll l = 0 , r = 3e9 , mid;
    while( l <= r ) {
        mid = l + r >> 1;
        if( chk( mid ) ) l = mid + 1;
        else r = mid - 1;
    }
    cout << l << endl;
}

signed main() {
    sieve();
//    freopen("input","r",stdin);
//    freopen("fuckout","w",stdout);
    int T;cin >> T;while( T-- ) solve();
//    solve();
}