解题关键：由容斥原理得，num=1的倍数的数量−一个质数平方数(9,25,49...)的倍数的数量+两个质数的积平方数(36,100,225...)的数量−三个质数......
这道题用莫比乌斯的正向函数表达式理解较容易
此题让自己理解了只要与倍数相关即可用mobius。
此题还需要注意的一点，是平方数只需要反演质数。貌似是常识
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<iostream>
using namespace std;
typedef long long ll;
ll t,n;
inline ll read(){
char k=;char ls;ls=getchar();for(;ls<''||ls>'';k=ls,ls=getchar());
ll x=;for(;ls>=''&&ls<='';ls=getchar())x=(x<<)+(x<<)+ls-'';
if(k=='-')x=-x;return x;
}
//莫比乌斯函数线性筛法
const int maxn=+;
bool vis[maxn];
int prime[maxn],mu[maxn];
void init_mu(int n){
int cnt=;
mu[]=;
for(int i=;i<n;i++){
if(!vis[i]){
prime[cnt++]=i;
mu[i]=-;
}
for(int j=;j<cnt&&i*prime[j]<n;j++){
vis[i*prime[j]]=;
if(i%prime[j]==) {mu[i*prime[j]]=;break;}
else { mu[i*prime[j]]=-mu[i];}
}
}
} bool check(ll x){
ll ans=;
for(ll i=;i*i<=x;i++){
ans+=mu[i]*(x/(i*i));
}
return ans>=n;
} ll erfen(ll l,ll r){
while(l<r){
ll mid=(l+r)>>;
if(check(mid)) r=mid;
else l=mid+;
}
return r;
}
int main(){
init_mu();
t=read();
while(t--){
n=read();
printf("%lld\n",erfen(, ));
} }