#include <fstream>
#define NMax 1000000
using namespace std;
ifstream f ("divprim.in");
ofstream g ("divprim.out");
int i, j, k, p[78500], nr, ok, nrdiv, t, l, n;
bool viz[NMax+5];
int main ()
{
    viz[1]=1;
    for (i=2; i<=NMax; i++){
        if (viz[i]==0){
            p[++k]=i;
            for (j=2; j*i<=NMax; j++)
                viz[i*j]=1;
        }
    }

    f >> t;
    for (l=1; l<=t; l++){
        f >> n >> k;
        ok=0;
        while (!ok && n>0){
            n--;
            nr=1;
            nrdiv=0;
            while (p[nr]<=n){
                if (n%p[nr]==0) nrdiv++;
                nr++;
            }
            if (nrdiv==k){
                ok=1;
                g << n << '\n';
                break;
            }
            else n--;
        }
        if (!ok) g << 0 << '\n';
    }
    return 0;
}