#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const int inf=1<<30; const ll INF=1LL<<62; typedef pair P; typedef pair PP; const ll MOD=998244353; const int MAXN=3*1000000; vector is_prime(MAXN+1,true); vector cnt_sum(MAXN+1,0); void init(){ is_prime[0]=is_prime[1]=false; for(int i=2;i<=MAXN;i++){ if(is_prime[i]){ for(int j=2*i;j<=MAXN;j+=i){ is_prime[j]=false; } } } //cnt_sum[i]:[1,i]の範囲での素数の個数 for(int i=1;i<=MAXN;i++){ cnt_sum[i]=cnt_sum[i-1]+(is_prime[i]?1:0); } } enum{ FIRST, SECOND, }; int solve(){ int N; cin>>N; //(N/2,N)の範囲で素数の個数を数える int fN = cnt_sum[N-1] - cnt_sum[N/2]; int c = N-fN-2; if(is_prime[N]){ //Nが素数 return SECOND;//後 } if(c%2==1){ return FIRST;//先 }else{ return SECOND;//後 } } int main(){ int T; cin>>T; init(); vector ans(T); for(int t=0;t