#include <iostream>
#include <fstream>
using namespace std;
ifstream in("divprim.in");
ofstream out("divprim.out");
const int MAX = 1000000;
int ciur[MAX+1];
int main()
{
    int t;
    in>>t;
    for(int i=2; i<=MAX; ++i)
    {
        if(ciur[i]==0)
            for(int d=2*i; d<=MAX; d=d+i)
                ciur[d]++;
    }
    for(int test=0; test<t; ++test)
    {
        int n,k;
        in>>n>>k;
        int nr=n;
        while(nr>1 && ciur[nr]!=k)
            --nr;
        if(ciur[nr]==k)
            out<<nr<<'\n';
        else if(ciur[nr-1]==k && nr>1)
            out<<nr-1<<'\n';
        else
            out<<0<<'\n';
    }
    return 0;
}