#include <iostream>
#include <fstream>
#include <vector>
#define NMAX 1000010
using namespace std;
vector<int> v[8];
int ciur[NMAX];
void faCiur();

int main()
{
    int t,n,k,st,dr,mij;
    ifstream f("divprim.in");
    ofstream g("divprim.out");
    faCiur();
    f >> t;
    while(t--){
        f >> n >> k;
        st = 0;
        dr = v[k].size();
        while(st<=dr){
            mij = (st + dr)/2;
            if(v[k][mij] > n)   dr = mij - 1;
            else st = mij + 1;
        }
        if(dr  < v[k].size() )   g << v[k][dr] << '\n';
        else g << 0 << '\n';
    }
    f.close();
    g.close();
    return 0;
}

void faCiur(){
    for(int i=2;i<NMAX;i++){
        if(ciur[i] == 0){
            for(int j=i;j<NMAX;j+=i)
                ciur[j]++;
        }
        v[ciur[i]].push_back(i);
    }
}