primos

#include<bits/stdc++.h>
using namespace std;
const int max = 100010;
int eh_primo[12010000];
vector<int> arr;
void crivo(int n){
    for (int i = 2; i <= n; i++){
        eh_primo[i] = -1;
    }
    for(int i = 2; i <= n; i++){
        if(eh_primo[i] == -1){
            eh_primo[i] = i;
            for (int j = i+i; j <= n; j += i){
                eh_primo[j] = 0;
            }
        }
    }
}
int busca_bin(int prim){
    int ini = 0, fim = (arr.size()), meio;
    while(ini <= fim){
        meio = (ini+fim)/2;
        if(arr[meio] == prim) return meio;
        if(arr[meio] > prim) fim = meio -1;
        if(arr[meio] < prim) ini = meio + 1;
    }
    return -1;
}
int main(){
    int n, prim;
    cin >> n;
    crivo(12000000);
    for(int i = 1; i <= 12000000; i++){
        if(eh_primo[i] != 0) arr.emplace_back(eh_primo[i]);
    }
    while(n--){
        cin >> prim;
        cout << (busca_bin(prim)+1) << endl;
    }
    return 0;
}