11415

#include <iostream>
#include <math.h>
#include <vector>

#define ull unsigned long long
#define SIZE 2703664
using namespace std;

int prime[1700];//3200
ull factor[SIZE];
int arr[10000001];
vector<int> v;

void primeGenerator()
{
	double p = sqrt(1700);
	for(int i=3;i<p;i+=2)
	{
		if(prime[i]==0)
		{
			for(int j=i+i;j<1700;j+=i)
			prime[j]=1;
		}
	}

	v.push_back(2);

	for(int i=3;i<1700;i+=2)
	{
		if(prime[i]==0)
		v.push_back(i);
	}
}


void countfactor()
{
	int tmp;
	factor[0]=1;

	factor[1]=1;

	factor[2]=1;


	for(int i=3;i<SIZE;i++)
	{
		tmp = i;
		int j=0;
		factor[i]=0;
		while(tmp>=(v[j]*v[j]))
		{
			if(tmp%v[j]==0)
			{
				tmp/=v[j];
				factor[i]++;
				j=-1;
			}
			j++;

			if(j==v.size())
			break;

		}
		if(tmp>1)
		factor[i]++;

		factor[i]+=factor[i-1];


	}

}

int main()
{
	primeGenerator();
	countfactor();

	ull low,mid,high;
	ull n,ans=0;
	int t;
	cin>>t;
	while(t--)
	{
		cin>>n;
		low=0;
		mid=SIZE/2;
		high=SIZE;
		ans = 0;
		if(arr[n])
		{
			cout<<arr[n]<<"\n";
			continue;
		}
		while((high-low)>1)
		{
			if(factor[mid]<=n)
			{
				low=mid;
				mid=(low+high)/2;
				//ans=high;
			}
			else
			{
				high=mid;
				mid=(low+high)/2;
				//ans=low;
			}
		}

		if(factor[mid+1]>n && factor[mid]<=n)
		{
			arr[n]=mid+1;
		}
		cout<<arr[n]<<"\n";
	}

	return 0;
}