#include <fstream>
#include <vector>
using namespace std;

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

vector<int>divtot[9];

int divizori[1000010];

int main(){
    int i,j;
    for(i = 2; i <= 1000000; i++){
        if(!divizori[i]){
            divizori[i] = 1;
            for(j = i+i; j <= 1000000; j+=i){
                divizori[j]++;
            }
        }
    }

    for(i = 1; i <= 1000000; i++){
        divtot[divizori[i]].push_back(i);
    }

    int t,n,k,st,dr,mij;
    fin>>t;
    for(;t--;){
        fin>>n>>k;
        st = 0,dr=divtot[k].size()-1;
        int rezultat = -1;
        while(st <= dr){
            mij = (st+dr)/2;
            if(divtot[k][mij] <= n)st = mij+1,rezultat = divtot[k][mij];
            else dr = mij-1;
        }
        if(rezultat == -1) fout<<"0"<<"\n";
        else fout<<rezultat<<"\n";
    }
}