#include <fstream>
using namespace std;

#define m 1000001

int ciur[m];

void ciurr ()
{
    int i, j;
    for (i=2; i<m; i+=2){
        ciur[i] ++;
    }
    for (j=3; j<m; j+=2){
        if (ciur[j] == 0){
            for (i=j; i<m; i+=j){
                ciur[i] ++;
            }
        }
    }
}

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

    ciurr ();

    int t, n, k;

    in >> t;

    while (t){
        t --;
        in >> n >> k;
        ciur[0] = k;
        while (ciur[n] != k){
            n --;
        }
        out << n << endl;
    }

    return 0;
}