#include <bits/stdc++.h> using namespace std; inline int Read() { int x = 0; char ch = getchar(); for(;ch < '0' || ch > '9';ch = getchar()); for(;ch >= '0' && ch <= '9';ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48); return x; } int ans1[9804]; int ans2[25001]; int main() { int t = Read(),cnt = 0; for(int i = 1;i <= 5000;i++) { bool flag = 0; for(int j = 1;j < i;j++) if((j * (i - j)) % i == 0) { flag = 1; break; } if(flag) ans1[++cnt] = i; } cnt = 0; for(int i = 1;i <= 5000;i++) { if(ans1[cnt + 1] == i) cnt++; ans2[i] = cnt; } while(t--) { int n = Read(); if(n <= 5000) printf("%d\n",ans2[n]); } return 0; }