#include<bits/stdc++.h>
using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");
int t,n,k,nr;
int main()
{
    f>>t;
    int v[]={0,2,3,5,7,11,13,17};
    for(int i=1;i<=t;i++)
    {
        f>>n>>k;
        nr=1;
        for(int j=1;j<=k;++j)
            nr*=v[j];
        if(nr<=n)
            g<<nr<<'\n';
        else
            g<<0<<'\n';
    }
    return 0;
}