二分答案，然后用莫比乌斯函数作为容斥系数，计算当前枚举的mid内有几个满足要求的数

#include
    
     #include
     
      #include
      
       using namespace std;const int N=50005;int t,k,mb[N],q[N],tot;bool v[N];int read(){    int r=0;    char p=getchar();    while(p>'9'||p<'0')        p=getchar();    while(p>='0'&&p<='9')    {        r=r*10+p-48;        p=getchar();    }    return r;}bool ok(long long x){    long long sum=0ll;    for(int i=1;i*i<=x;i++)        sum+=x/(i*i)*mb[i];    return sum>=k;}int main(){    mb[1]=1;    for(int i=2;i<=50000;i++)    {        if(!v[i])        {            q[++tot]=i;            mb[i]=-1;        }        for(int j=1;j<=tot&&i*q[j]<=50000;j++)        {            int k=i*q[j];            v[k]=1;            if(i%q[j]==0)            {                mb[k]=0;                break;            }            mb[k]=-mb[i];        }    }    t=read();    while(t--)    {        k=read();        long long l=k,r=2e9,ans;        while(l<=r)        {            long long mid=(l+r)>>1;            if(ok(mid))                r=mid-1,ans=mid;            else                l=mid+1;        }        printf("%lld\n",ans);    }    return 0;}