奇怪的问题

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;

const int maxn = 2e6+5e5;

int pre[maxn];
bool vis[maxn];
vector<int> Prime;

void isprime(){
	for(int i = 2; i < maxn-100; i++){
		if(!vis[i]) Prime.push_back(i);
		//cout << Prime.size() << " ";
		for(int j = 0; j < Prime.size(); j++){
			//cout << Prime.size() << " " << j << "\n";
			if(1ll * i * Prime[j] > maxn) break;
			vis[i*Prime[j]] = true;
			if(i % Prime[j] == 0) break;
		}
	}
}

int main(){
	int T;
	scanf("%d", &T);
	int cnt = 0;
	vis[0] = vis[1] = true;
	isprime();
	//cout << Prime.size();
	for(int i = 1; i < maxn-100; i++){
		if(!vis[i]) pre[i] = ++cnt;
		else pre[i] = cnt;
	}
	while(T--){
		int n, p = 0;
		long long ans = 0;
		scanf("%d", &n);
		while(n){
			if(n & 1){
				ans += pre[(1<<(p+1))-1] - pre[(1<<p)-1];
			}
			n >>= 1;
			p++;
		}
		printf("%lld\n", ans);
	}
	return 0;
}