#include <algorithm>
#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <stack>
#include <cmath>
// #include <bits/stdc++.h>
#define in  fin
#define out fout

using namespace std;
const int NMAX = 1000001;

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

bool c[NMAX];
int divs[NMAX];
vector<int> nr[8]; // numerele care au k divizori

void ciur(){
    c[0] = c[1] = 1;
    for(int i = 2; i * i < NMAX; i++){
        if(!c[i]){
            for(int j = 2 * i; j < NMAX; j += i){
                divs[j]++;
                c[j] = 1;
            }
        }
    }

    for(int i = 0; i < NMAX; i++){
        if(divs[i] <= 7) nr[ divs[i] ].push_back(i);
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    in.tie(NULL);

    ciur();
    nr[0].push_back(1);

    int t; in >> t;
    for(int ii = 0; ii < t; ii++){
        int n, k; in >> n >> k;
        int poz = upper_bound(nr[k].begin(), nr[k].end(), n) - nr[k].begin() - 1;
        if(poz < 0) out << "0\n";
        else out << nr[k][poz] << "\n";
    }
    
    return 0;
}