#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")

using namespace std;

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

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

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

int main (){
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);

    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);

    p[0] = {-1, 0};
    for(int i=1; i<=LIM; i++){
        if(p[i].first != p[i-1].first)
            seq[ p[i].first ].first = i;
        seq[ p[i].first ].second = i;
    }

    int teste;
    fin>>teste;
    while(teste--){
        fin>>n>>k;

        found = false;
        lower = seq[k].first;
        upper = seq[k].second;
        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;
}