#include <fstream>
using namespace std;

const int maxn = 1000000;
ifstream fin("divprim.in");
ofstream fout("divprim.out");

int cnt[maxn+1];
int best[8][maxn+1];

int main()
{

    for (int i=2; i<=maxn; i++)
    {
        if (cnt[i]==0)
        {
            for (int j=i; j<=maxn; j+=i)
            {
                cnt[j]++;
            }
        }
    }

    for (int k=0; k<=7; k++)
    {
        best[k][0]=0;
        for (int x=1; x<=maxn; x++)
        {
            if (cnt[x]==k) best[k][x]=x;
            else best[k][x] = best[k][x-1];
        }
    }

    int t;
    fin>>t;
    while (t--)
    {
        int n, k;
        fin>>n>>k;
        if (k>7) fout<<0<<'\n';
        else fout<<best[k][n]<<'\n';
    }

    return 0;
}