#include <iostream>
#include <fstream>

using namespace std;
ifstream f ("divprim.in");
ofstream g ("divprim.out");
long long MAX=1000000;
int mak[8][1000005];
int fprimi[1000005];
int main()
{
    for(int i=2;i<=MAX;i++)
    {
        if(fprimi[i]==0)
        {
            for(int j=i;j<=MAX;j+=i)
            {
                fprimi[j]++;
            }
        }
    }
        for(int i=1;i<=MAX;++i)
        {
            for(int y=0;y<=7;++y)
            {
                mak[y][i]=mak[y][i-1];
            }
            if(fprimi[i]<=7)
            mak[fprimi[i]][i]=i;
        }
        int n,k;
        int t;
        f>>t;
        for(int i=1;i<=t;++i)
        {
            f>>n>>k;
            g<<mak[k][n]<<"\n";
        }
    return 0;
}