UVa11415

/*Basic info
Problem :
Date :
Author : Shesher
*/

#include<bits/stdc++.h>

using namespace std;

///Template
#define in1()    freopen("C:\\Users\\SHESHER\\Rest\\Desktop\\MY COMPUTER\\Code\\Template\\input.txt", "r", stdin);
#define out1()   freopen("C:\\Users\\SHESHER\\Rest\\Desktop\\MY COMPUTER\\Code\\Template\\output.txt", "w", stdout);


//Data types
#define lo      long
#define ll      long long
#define llu     unsigned long long

//loop
#define f1(i,x,y)   for(int i=x;i<=y;i++)

//Constants
#define MAX     100007
#define MOD     1000000007
#define PI      acos(-1.0)

//STL
#define vout(v)    for(int i=0;i<v.size();i++){cout<<v[i]; if(i==v.size()-1) cout<<endl; else cout<<" ";}

//Scan
#define sc(x)    scanf("%d", &x)
#define scl(x)   scanf("%lld", &x)

//Print
#define pa(a,i,n)  for(int i=0;i<n;i++){ cout<<a[i]; if(i==n-1) cout<<endl; else cout<<" ";}

#define mset(flag)  memset(flag,0,sizeof(flag))

bool cmp(int a, int b){ return a>b; }

int NOPF(int n)
{
    int cunt=0;
    while(n%2==0){
        cunt++;
        n/=2;
    }
    for(int i=3;i<=sqrt(n);i+=2){
        if(n%i==0){
            while(n%i==0){
                cunt++;
                n/=i;
            }
        }
    }
    if(n>1) cunt++;

    return cunt;
}

ll ar[10011000];
void precal()
{
    ar[0]=1;
    ar[1]=1;
    ar[2]=1;
    ar[3]=2;
    for(int i=4;i<=10000010;i++){
        ar[i]=ar[i-1]+NOPF(i);
    }
}

int calculate(int n)
{
    int l=0, r=10000000, mid;
    int temp=-1;

    while(l<=r){
        mid=(l+r)/2;
        // cout<<l<<" "<<mid<<" "<<r<<" "<<ar[mid]<<endl;
        if(ar[mid]<=n){
            temp=mid;
            l=mid+1;
        }
        else r=mid-1;
    }

    return temp;
}

int main()
{
    // in1();
    // out1();
    // clock_t tStart = clock();

    ///CODE STARTS HERE
    precal();
    // cout<<ar[10000000]<<endl;
    int t;
    sc(t);
    while(t--){
        int n;
        sc(n);
        cout<<calculate(n)+1<<endl;
    }

    // printf("\n>>Runtime: %.10fs\n", (double) (clock() - tStart) / CLOCKS_PER_SEC);


    return 0;
}