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

using namespace std;

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

const int LIM = 1e6;

int dpr[LIM + 5];
int n, k;

vector <int> num[15];
int st, md, dr, found;

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

    dpr[1] = 0;
    for(int i=2; i<=LIM; i++)
        if(!dpr[i])
            for(int j=i; j<=LIM; j+=i)
                dpr[j]++;

    for(int i=1; i<=LIM; i++)
        num[ dpr[i] ].push_back(i);

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

        found = false;
        st = 0;
        dr = (int)num[k].size();
        while(st <= dr){
            md = (dr - st) / 2 + st;

            if(num[k][md] <= n){
                found = num[k][md];
                st = md + 1;
            }else
                dr = md - 1;
        }
        fout<<found<<"\n";
    }
    return 0;
}