#include <bits/stdc++.h>

using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
const int NMAX=1000000;
int c[NMAX+5];
int v[8];
void ciur()
{
    int i, j, maxi=0;
    for(i=2; i<=NMAX; i+=2)
    {
        c[i]++;
    }
    for(i=3; i<=NMAX; i+=2)
    {
        if(c[i]==0)
        {
            for(j=i; j<=NMAX;j+=i)
            {
                c[j]++;
                if(v[c[j]]==0)
                    v[c[j]]=j;
            }
        }
    }
}
int cautarek(int n, int k)
{
    int i;
    if(k==0)
        return 1;
    for(i=n; i>=v[k]; --i)
    {
        if(c[i]==k)
            return i;
    }
    return 0;
}
int main()
{
    int t, n, k, i;
    fin >> t;
    ciur();
    //*
    for(i=1; i<=t; ++i)
    {
        fin >> n >> k;
        fout << cautarek(n,k) << "\n";
    }
    //*/
    return 0;
}