#include <iostream>
#include <fstream>


#define max 1000000

using namespace std;


int v[max+1],t,k;
long b;

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

    for(long i = 2;i<=max/2;i++)
        if(v[i] == 0)
            for(long j = i+i;j<=max;j+=i)
                v[j]++;

    f>>t;
    for(int i = 0;i<t;i++)
    {
        f>>b>>k;
        for(long j = b;j>=3;j--)
        {
            if(v[j] == k)
            {
                g<<j<<'\n';
                break;
            }
            if(j == 3) g<<"0\n";
        }

    }



    f.close();
    g.close();

    return 0;
}