#include <fstream>

using namespace std;

ifstream f("divprim.in");
ofstream g("divprim.out");
int divz[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();

    f>>q;
    int n, k;
    while(q--)
    {
        f>>n>>k;
        if(k == 0)
        {
            g<<1<<'\n';
        }
        else
        {
            for(int i = n; i>=0; i--)
            {
                if(divz[i] == k)
                {
                    g<<i<<'\n';
                    break;
                }

                if(i == 0)
                {
                    g<<0<<'\n';
                }
            }

        }
    }

    return 0;
}