#include <fstream>

using namespace std;
ifstream cin("divprim.in");
ofstream cout("divprim.out");

const int nmax = 1000000;
int divizori[1 + 5], divizori1[nmax + 5], divizori2[nmax + 5], divizori3[nmax + 5], divizori4[nmax + 5], divizori5[nmax + 5], divizori6[nmax + 5], divizori7[nmax + 5], k1, k2, k3, k4, k5, k6, k7;


int main()
{
    int i, j;
    divizori[1] = 0;
    for ( i = 2; i <= nmax; ++i )
        if ( divizori[i] == 0 )
            for ( j = i; j <= nmax; j += i )
                ++divizori[j];
    for ( i = 2; i <= nmax; ++i )
    {
        if ( divizori[i] == 1 )
            divizori1[++k1] = i;
        if ( divizori[i] == 2 )
            divizori2[++k2] = i;
        if ( divizori[i] == 3 )
            divizori3[++k3] = i;
        if ( divizori[i] == 4 )
            divizori4[++k4] = i;

        if ( divizori[i] == 5 )
            divizori5[++k5] = i;
        if ( divizori[i] == 6 )
            divizori6[++k6] = i;
        if ( divizori[i] == 7 )
            divizori7[++k7] = i;
    }
    int t, n, k;
    cin >> t;
    while ( t-- )
    {
        cin >> n >> k;
        int mij, sol = 0,st = 1, dr;
        if ( k == 1 )
        {
            dr = k1;
            while ( st <= dr )
            {
                mij = (st + dr) / 2;
                if ( divizori1[mij] <= n )
                {
                    sol = divizori1[mij];
                    st = mij + 1;
                }
                else
                    dr = mij - 1;
            }
        }

        if ( k == 2 )
        {
            dr = k2;
            while ( st <= dr )
            {
                mij = (st + dr) / 2;
                if ( divizori2[mij] <= n )
                {
                    sol = divizori2[mij];
                    st = mij + 1;
                }
                else
                    dr = mij - 1;
            }
        }





        if ( k == 3 )
        {
            dr = k3;
            while ( st <= dr )
            {
                mij = (st + dr) / 2;
                if ( divizori3[mij] <= n )
                {
                    sol = divizori3[mij];
                    st = mij + 1;
                }
                else
                    dr = mij - 1;
            }
        }




        if ( k == 4 )
        {
            dr = k4;
            while ( st <= dr )
            {
                mij = (st + dr) / 2;
                if ( divizori4[mij] <= n )
                {
                    sol = divizori4[mij];
                    st = mij + 1;
                }
                else
                    dr = mij - 1;
            }
        }



        if ( k == 5 )
        {
            dr = k5;
            while ( st <= dr )
            {
                mij = (st + dr) / 2;
                if ( divizori5[mij] <= n )
                {
                    sol = divizori5[mij];
                    st = mij + 1;
                }
                else
                    dr = mij - 1;
            }
        }



        if ( k == 6 )
        {
            dr = k6;
            while ( st <= dr )
            {
                mij = (st + dr) / 2;
                if ( divizori6[mij] <= n )
                {
                    sol = divizori6[mij];
                    st = mij + 1;
                }
                else
                    dr = mij - 1;
            }
        }


        if ( k == 7 )
        {
            dr = k7;
            while ( st <= dr )
            {
                mij = (st + dr) / 2;
                if ( divizori7[mij] <= n )
                {
                    sol = divizori7[mij];
                    st = mij + 1;
                }
                else
                    dr = mij - 1;
            }
        }

        if ( k == 0)
            sol = 1;



        cout << sol << '\n';
    }

    return 0;
}