#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");
int t, n, k;
int pp[1000005];
vector <int> num[10];
void ciur() {
    for(int i=2; i<=1000000; i++) {
        if(pp[i]==0) {
            for(int j=2*i; j<=1000000; j+=i){
                pp[j]++;
            }
        }
    }
}
int main() {
    ciur();
    for(int i=1; i<=1000000; i++) {
        num[pp[i]].push_back(i);
    }
    f>>t;
    while (t) {
        f>>n>>k;
        int poz=upper_bound(num[k].begin(), num[k].end(), n)-num[k].begin();
        if(poz) {
            g<<num[k][poz-1]<<'\n';
        } else {
            g<<"0"<<'\n';
        }
        t--;
    }
    return 0;
}