#include using namespace std; int p[1000000]; vector V; void sieve() { int i,j,k; for(i=2;i<=1000000;i++) { p[i]=1; } for(i=2;i*i<=1000000;i++) { if(p[i]==1) { for(j=2*i;j<=1000000;j+=i) { p[j]=0; } } } for(i=2;i<=1000000;i++) { if(p[i]==1) V.push_back(i); } } int main() { int N,Q,i,j,k; sieve(); cin>>Q; while(Q--) { cin>>N; int cnt=0; for(i=0;i