#include using namespace std; vectorv; void Sieve() { // Create a boolean array "prime[0..n]" and initialize // all entries it as true. A value in prime[i] will // finally be false if i is Not a prime, else true. bool prime[299995]; memset(prime, true, sizeof(prime)); for (int p=2; p*p<=299995; p++) { // If prime[p] is not changed, then it is a prime if (prime[p] == true) { // Update all multiples of p for (int i=p*2; i<=299995; i += p) prime[i] = false; } } for(int i=2; i<=299995 ; i++){ if(prime[i])v.push_back(i); } } int main(){ int t; scanf("%d",&t); Sieve(); while(t--){ int n; scanf("%d",&n); int alice=0,bob=0; //int a[n+7]; memset(a,0,sizeof(a)); for(int i=0; i