#include <iostream>
#include <fstream>
#include <bitset>

using namespace std;

bitset<1000001> p;
int divprimi[1000002], divizori[300000][8], nr[8];
ifstream in("divprim.in");
ofstream out("divprim.out");
int i, j, rez, k, n, t, st, dr, mij;
bool gasit = false;
int main()
{
    for(i = 2; i <= 1000; i++) {
        if(p.test(i) == 0) {
            divprimi[i] = 1;
            for(j = 2*i; j <= 1000000; j=j+i) p.set(j, 1), divprimi[j]++;
        }
    }
    j = 0;
    p.set(1, 1);

    for(i = 0; i <= 7; i++) nr[i] = 1;
    for(i = 1; i <= 1000000; i++) if(divprimi[i] <= 7) divizori[nr[divprimi[i]]][divprimi[i]] = i, nr[divprimi[i]]++;

    in >> t;
    for(i = 1; i <= t; i++) {
        in >> n >> k;
        st=1, dr=nr[k];
        if(k == 0) out << "1\n";
        else if(divizori[1][k] > n) out << "0\n";
        else {
            while(st < dr) {
                mij = (st+dr)/2;
                if(divizori[mij][k] <= n) {
                    if(divizori[mij+1][k] <= n) st = mij+1;
                    else out << divizori[mij][k] << "\n", st = dr+1;
                } else dr = mij;
            }
        }
    }
    return 0;
}