#include<fstream>
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
unsigned t,k,n,i,j;
char v[1000001];
int a[1000001][8];

void ciur(unsigned x)
{
	for(i=2; i<=x; i++)
    {
        if(v[i]==0)
            for(j=i; j<=x; j+=i)
                v[j]++;
    }
}



int main()
{
	fin>>t;
	
	ciur(1000000);
	
	for(i=2;i<=1000000;i++)
	{
		for(j=1;j<=7;j++)
		{
			a[i][j]=a[i-1][j];
		}
		a[i][v[i]]=i;
	}
	
	/*for(i=2;i<=1000000;i++)
	{
		for(j=1;j<=7;j++)
		{
			fout<<a[i][j]<<" ";
		}
		fout<<"\n";
	}*/
	
	
	for(i=1;i<=t;i++)
	{
		fin>>n>>k;
		fout<<a[n][k]<<"\n";
	}
}