#include <bits/stdc++.h>

using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");
int n,m,k,p=1,i,j;
bitset<1000010> pr;
bool ok=true;

int main()
{
    pr[0]=pr[1]=1;
    for(i=4; i<=1000000; i+=2)
        pr[i]=1;
    for(i=3; i<=1000; i+=2)
        if(!pr[i])
            for(j=i*i; j<=1000000; j+=i)
                pr[j]=1;
    f>>n;
    for(int i=1; i<=n; i++)
    {
        p=1;
        int x=3;
        f>>m>>k;
        while(k)
        {
            if(pr[x]==0&&k!=1)
            {
                k--;
                ok=false;
                p*=x;
            }
            else if(pr[x]==0&&k==1&&ok==true)
                p*=x;
            x++;
        }
        if(p<=m)
            g<<p<<'\n';
        else
            g<<"0\n";
    }
    return 0;
}