#include <fstream>
#include <iostream>

using namespace std;

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

const int NMAX = 1e6;
int v[NMAX+1];

int caut(int n, int k){
    int j = n;
    while(j >= 1){
        if(v[j] == k)
            return j;
        j--;
    }
    return 0;
}

int main()
{
    for(int i=2; i*2 <= NMAX; i++)
        if(!v[i])
            for(int j = i; j<=NMAX; j+=i)
              v[j]++;
    int t;
    f>>t;
    for(int i=1; i<=t; i++){
        int n, k;
        f>>n>>k;
        g<<caut(n, k)<<"\n";
    }
                
    

    return 0;
}