#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

const int N = 1e6, D = 7;
vector <int> mat[D + 1];
int ciur[N + 1];

int main(){
    for(int i = 2; i <= N; i++)
        if(!ciur[i])
            for(int div = i; div <= N; div += i)
                ciur[div]++;
    for(int i = 1; i <= N; i++)
        if(ciur[i] <= 7)
            mat[ciur[i]].push_back(i);
    for(int i = 1; i <= D; i++) sort(mat[i].begin(), mat[i].end());
    int t;
    fin >> t;
    while(t--){
        int n, k;
        fin >> n >> k;
        int st = 0, dr = mat[k].size();
        while(dr - st > 1)
            mat[k][(st + dr) / 2] > n ? dr = (st + dr) / 2 : st = (st + dr) / 2;
        mat[k][st] <= n ? fout << mat[k][st] << '\n' : fout << 0 << '\n';
    }
    return 0;
}