#include <iostream>

#include <fstream>

#include <string.h>

#include <algorithm>

#include <math.h>

using namespace std;



ifstream cinn ("divprim.in");

ofstream coutt ("divprim.out");



int e[1000002],prime[1000002],nmp[1000000],k;



void eratostene()
{

    for(int i=2; i<sqrt(1000000); i++)
    {

        if(e[i] == 0)
        {

            for(int j = 2; j<1000000/i; j++)
            {

                e[i*j] = 1;

            }



        }



    }



}



void vectoreratostene()
{



    for(int i =0; i<1000000; i++)
    {

        if(e[i] == 0)
        {

            prime[k] = i;

            k++;

        }

    }



}



void NrMultipliiPrimi()
{

    for(int i = 0; i<k; i++)
    {

        for(int j = 1; j<k/(i+1); j++)
        {
            if(nmp[j*prime[i]]<7)
            nmp[j*prime[i]]+=1;

        }

    }


}



int main()

{

    int n;

    eratostene();

    vectoreratostene();

    NrMultipliiPrimi();

    cinn >>n;



    for(int i =0; i<n; i++)
    {

        int x,y;

        cinn >> x >>y;



        int j,bec = 1;

        for( j = x ; j>0; j--)
        {

            if(nmp[j] == y+1)
            {

                coutt << j<<endl;

                j = -10;

                bec = 0;

            }



        }

        if(bec == 1)
        {

            coutt << 0 <<endl;

        }



    }



}