rt,这道题有一种$O(nk)$的做法，$k$ 是 $10^4$ 以内质数个数，即 $1229$。但是这样的复杂度应该是勉勉强强需要卡常才能过的，因为判断整除需要取模，取模的常数很大。题解区也有一些用了这种做法的，或许可以被卡掉？
一种更好的思路是每次除完之后判断一下剩下的是不是一个大质数，如果是则直接退出循环，极限情况下时间复杂度是 $O(V+Tk^2+N)$，$V$ 是线性筛的复杂度，每组数据最劣会被卡到 $O(k^2+n)$，总的复杂度就是 $O(Tk^2+N)$
当然也可以用一些复杂度低于线性的质数筛