1 #include <iostream>
 2 #include<stdio.h>
 3 #include <algorithm>
 4 #include<string.h>
 5 #include<cstring>
 6 #include<math.h>
 7 #define inf 0x3f3f3f3f
 8 #define ll long long
 9 using namespace std;
10 const int maxx=3000086;
11 int prime[2000086];
12 bool vis[3000086];
13 int ans[1000086];
14 int cnt;
15 
16 void init()
17 {
18     cnt=0;
19     memset(vis,true,sizeof(vis));
20     vis[0]=vis[1]=false;
21     for(int i=2;i<=maxx;i++)//欧拉筛
22     {
23         if(vis[i])
24             prime[cnt++]=i;
25         for(int j=0;j<cnt && prime[j]*i<=maxx;j++)
26         {
27             vis[ prime[j]*i ]=false;
28             if( i%prime[j]==0 ) break;
29         }
30     }
31     memset(ans,0,sizeof(ans));
32     int p;
33     for(int k=1;k<=1000005;k++)
34     {
35         p=3*k+7;
36         if(vis[p])
37             ans[k]=ans[k-1]+1;
38         else
39             ans[k]=ans[k-1];
40     }
41 }
42 
43 int main()///hdu2973,威尔逊定理+前缀和
44 {
45     init();
46     int t,n;
47     scanf("%d",&t);
48     while(t--)
49     {
50         scanf("%d",&n);
51         printf("%d\n",ans[n]);
52     }
53     return 0;
54 }