#include <bits/stdc++.h>

using namespace std;

ifstream fin  ("divprim.in");
ofstream fout ("divprim.out");

const int LIM = 1e6;
pair<int, int> p[LIM + 5];

int n, k, lower, upper, st, md, dr, found, target;

int main (){
    p[1].first = 0;
    for(int i=2; i<=LIM; i++)
        if(p[i].first == 0)
            for(int j=i; j<=LIM; j+=i)
                p[j].first++;
    for(int i=1; i<=LIM; i++)
        p[i].second = i;
    sort(p+1, p+LIM+1);

    int teste;
    fin>>teste;
    while(teste--){
        fin>>n>>k;
        lower = 1;
        upper = LIM;
        found = false;

        st = 1;
        dr = LIM;
        while(st <= dr){
            md = (dr - st) / 2 + st;

            if(p[md].first < k)
                st = md + 1;
            else
                dr = md - 1;
        }
        lower = st;

        st = 1;
        dr = LIM;
        while(st <= dr){
            md = (dr - st) / 2 + st;

            if(p[md].first > k)
                dr = md - 1;
            else
                st = md + 1;
        }
        upper = dr;

        while(lower <= upper){
            md = (upper - lower) / 2 + lower;

            if(p[md].second <= n){
                found = p[md].second;
                lower = md + 1;
            }else
                upper = md - 1;
        }

        fout<<found<<"\n";
    }
    return 0;
}