要求第(k)个不是完全平方数的正整数倍的数，直接求显然十分暴力，于是考虑一下二分答案。
二分之后，问题转化为求([1,mid])这段区间内有多少个无完全平方因子的整数。
先考虑一下完全平方数对答案的贡献，(2^2)可以对其所有的倍数产生贡献，(3^2)可以对其所有的倍数产生贡献，但是我们发现(6^2)的倍数会被统计两次贡献，因此要减掉。不难看出这是个容斥原理。
答案的补集显然就是1个质数平方倍数的个数 - 2个质数乘积的平方倍数的个数 ...
即答案为偶数个质数的乘积的平方的倍数的个数-奇数个质数的乘积的平方的倍数的个数依次算下去。
列一下式子：
[ans = sum_{i=1}^{sqrt{n}} mu(i) lfloor frac{n}{i^2}
floor
]
这里用 (mu) 直接作为容斥系数，结合其定义不难发现这是对的。
然后直接二分答案即可。
复杂度(O(Tlog nsqrt{n}))