#include<fstream>

using namespace std;

	ifstream fin("divprim.in");
    ofstream fout("divprim.out");
	
int a[1000005], da[1000005][10];

int main()
{
    int n, nr, k, i, j;
    for(i=2;i<=1000005;i++)
    if(!a[i])
        for(j=i;j<=1000005;j+=i)
        a[j]++;
    for(i=2;i<1000001;i++)
    {
        for(j=0;j<=7;j++)
        da[i][j]=da[i-1][j];
        da[i][a[i]]=i;
    }
    fin>>nr;
    for(j=1;j<=nr;j++)
    {
        fin>>n>>k;
        fout<<da[n][k]<<"\n";
    }
    return 0;
}