#include<bits/stdc++.h>
#define ll long long
#define N ((int)6e4 + 5)
#define MOD ((int)1e9 + 7)
#define MAX ((int)1e9 + 7)
#define MAXL ((ll)1e18 + 7)
#define MAXP ((int)1e3 + 7)
#define thr 1e-8
#define pi acos(-1)  /// pi = acos ( -1 )
#define fastio ios_base::sync_with_stdio(false),cin.tie(NULL)
#define endl "\n"

using namespace std;

int isPrime[N/32 + 2];

bool IsPrime(int num) /// returns 1 for prime
{
    if(num == 2) return 1;
    if((num & 1) == 0)  return 0;
    int idx  = num >> 5 , bit = num & 31;
    if( ( isPrime[idx] & (1<<bit) ) != 0 ) return 0;
    else return 1;
}

vector < int > BitwiseSieve(int n)
{
    for(int i = 3; i * i <= n ; i += 2){
        if(IsPrime(i)){
            for(int j = i * i ; j <= n ; j += i<<1){
                int idx = j >> 5 , bit = j & 31;
                isPrime[idx] = isPrime[idx] | (1<<bit);
            }
        }
    }
    vector < int > prime;
    prime.push_back(2);
    for(int i = 3 ; i <= n ; i += 2){
        if(IsPrime(i)) prime.push_back(i);
    }
    return prime;
}