#include <fstream>
#include <vector>

using namespace std;

ifstream cin("divprim.in");
ofstream cout("divprim.out");

const int N = 1000001;

vector <int> a[100001];
int nr[N];

int caut(vector <int> v,int n){
    int r  = -1;
    int pas = 1 << 18;
    while(pas!=0){
        if(r+pas < v.size() && v[r+pas] <= n){
            r+=pas;
        }
        pas /= 2;
    }
    if(r == -1)
        return 0;
    return v[r];
}

int main()
{
    int t,k,i,div,j,n;
    for(i = 2;i < N;i++){
        if(nr[i] == 0){
            for(j=i;j<N;j+=i){
                nr[j]++;
            }
        }
    }
    for(i=1;i<N;i++){
        a[nr[i]].push_back(i);
    }

    cin >> t;
    for(i=0;i<t;i++){
        cin >> n >> k;
        cout << caut(a[k],n) << "\n";
    }
    return 0;
}