#include #include using namespace std;

const int MAX = 1e7 + 5; // 最大 n 是 1e7 vector is_prime(MAX, true); vector prefix(MAX, 0); // 前缀和：prefix[i] = 1~i 的素数个数

// 埃氏筛 + 预处理前缀和 void init() { is_prime[0] = is_prime[1] = false; for (long long i = 2; i * i < MAX; ++i) { if (is_prime[i]) { for (long long j = i * i; j < MAX; j += i) is_prime[j] = false; } }

// 计算前缀和
int cnt = 0;
for (int i = 0; i < MAX; ++i) {
    if (is_prime[i]) cnt++;
    prefix[i] = cnt;
}

}

int main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 加速输入输出（必须加！）

init(); // 只筛一次！

int t;
cin >> t;
while (t--) {
    int n;
    cin >> n;
    cout << prefix[n] << '\n'; // O(1) 输出答案
}
return 0;

}

#include<bits/stdc++.h> using namespace std; #define int long long int n,c,v[10000005],t; signed main(){ while(cin>>n){ if(n==0)return 0; for(int i=2;i<=n;i++){ if(v[i]==0){ for(int j=i+i;j<=n;j+=i){ v[j]=1; } } } for(int i=2;i<=n;i++){ if(v[i]==0)c++; } cout<<c<<endl; c=0; } return 0; }

#include <bits/stdc++.h>
using namespace std;
int n=1,ans;
bool isp[10000010];
int main(){
while(n){
cin>>n;
if(n==0){
break;
}
for(int i=2;i<=n;i++){
if(isp[i]==0){
ans++;
for(int j=2;j*i<=n;j++){
isp[i*j]=1;
}
}
}
cout<<ans<<endl;
ans=0;
}
    return 0;
}