#include <fstream>
#include <algorithm>

using namespace std;

ifstream f("divprim.in");
ofstream g("divprim.out");
int divz[1000005];
int v[10][1000005];
int q;

/*int ciur[1000005];
void build_ciur()
{
    ciur[0] = ciur[1] = 1;
    for(int i = 2; i*i<=1000000; i++)
    {
        if(ciur[i] == 0)
        {
            for(int j = 2; i*j<=1000000; j++)
            {
                ciur[i*j] = 1;
            }
        }
    }
}*/

void build_div()
{
    for(int i = 2; i<=1000000; i++)
    {
        if(divz[i] == 0)
        {
            for(int j = 1; i*j<=1000000; j++)
            {
                divz[i*j]++;
            }
        }
    }
}

int main()
{
    build_div();

    for(int i = 1; i<=1000000; i++)
    {
        v[divz[i]][0]++;
        v[divz[i]][v[divz[i]][0]] = i;
    }
    for(int i = 0; i<=7; i++)
    {
        sort(v[i]+1, v[i]+v[divz[i]][0]+1);
    }

    f>>q;
    int n, k;
    int st, dr, m, ans;
    while(q--)
    {
        f>>n>>k;
        st = 1;
        dr = v[k][0];
        ans = 0;
        while(st <= dr)
        {
            m = (st + dr) / 2;

            if(v[k][m] <= n)
            {
                ans = v[k][m];
                st = m + 1;
            }
            else
            {
                dr = m - 1;
            }
        }

        g<<ans<<'\n';
    }

    return 0;
}