#include <fstream>
#include <iostream>

using namespace std;

//bool v[1000001];
int d[1000001], nr[8], a[8][1000001];

/*int prime(int n)
{
    int i, j, a=0;
    for(i=2; i*i<=n; i++)
        if(!v[i])
            for(j=i*i;j<=n;j+=i)
                v[j]=true;
        for(i=2;i<=n;i++)
            if(!v[i])
                a++;
    return a;
}*/

int main()
{
    ifstream f("divprim.in");
    ofstream g("divprim.out");

    int i, n, k=0, pas, j, t;
    f>>t;
    for(i=2;i<1000001;i++)
        if(d[i]==0)
            for(j=i;j<1000001;j+=i)
                d[j]++;
    for(i=1;i<1000001;i++)
    {
        ++nr[d[i]];
        a[d[i]][nr[d[i]]]=i;
    }
    /*for(i=1;i<=7;i++)
        k+=nr[i];
    cout<<k;*/
    for(i=1;i<=t;i++)
    {
        f>>n>>k;
        /*j=1;
        pas=1<<20;
        while(pas!=0)
        {
            if(j+pas<=n && d[j+pas]==k)
                j+=pas;
            pas/=2;
        }
        if(d[j]==k)
            g<<j<<"\n";
        else
            g<<"0\n";*/
        j=1;
        while(a[k][j]<=n)
            j++;
        g<<a[k][j-1]<<"\n";
    }
    f.close();
    g.close();
    return 0;
}