#include <stdio.h>
#include <iostream>
#include <string.h>
using namespace std;
int prime[2000001] = {};
void taomang();

int main()
{
#ifndef ONLINE_JUDGE
   freopen ("input.txt", "r", stdin);
   freopen ("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int i,n,temp,j,dem;
    cin >> n;
    taomang();
    for (i = 1 ; i <= n ; i++)
    {
        cin >> temp;
        dem = 0;
         for (j = (temp + 1); j <= (2 * temp); j++)
        {
            if (prime[j] == 0)
            {
                dem++;
            }
        }
        cout << dem << endl;
    }
    return 0;
}
void taomang()
{
    int l = 2,k =  l * l;
    prime[0] = 1 ;
    prime[1] = 1;
    for (l = 2;l <= 2000000; l++)
    {
        if (prime[l] == 0)
        {

            for (k = (l * l); k <= 2000000 ; k = k + l)
            {
                prime[k] = 1;
            }
        }
    }
}