#include <bits/stdc++.h>
#define ll long long
#define inceput fin >> t
#define sfarsit return 0
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");


const int MAXVAL = 1e6;

bool ciur[MAXVAL + 1];
int t, n, k;
int lowest[10];
int nr_prime[80000];
int prime_divs[MAXVAL + 1];
ll sum;

vector <int> how_many[10];
/*
  2*3*5*7*11*13*17 = 510510
  2*3*5*7*11*13*17*19 = 9699690
  deci un numar <= 1e6 poate avea max 7 divizori primi
  10 pt siguranta
  vom calcula toti divizorii primi in O(n * log log n) (n = 1e6) folosind parcurgerile din ciurul lui eratostene
  de asemenea vom face o matrice in care tinem minte numerele cu i div primi
*/

void precalc() {
    int i, d, prim;
    for( i = 2; i * i <= MAXVAL; i++) {
        if( ciur[i] == 0 ) {
            for( d = i * i; d <= MAXVAL; d += i)
                ciur[d] = 1;
        }
    }
    int prime = 0;
    for( i = 2; i <= MAXVAL; i++) {
        if( ciur[i] == 0)
            nr_prime[++prime] = i;
    }
    for( i = 1; i <= prime; i++) {
        prim = nr_prime[i];
        //cout << prim << "\n";
        for( d = prim; d <= MAXVAL; d += prim ) {
            //cout << d << " ";
            prime_divs[d]++;
        }
        //cout << "\n";
    }
    prime_divs[0] = prime_divs[1] = 0;
    for( i = 1; i <= MAXVAL; i++) {
        int divprime = prime_divs[i];
        how_many[divprime].push_back(i);
    }
    lowest[1] = 2;
    for( i = 2; i <= 8; i++)
        lowest[i] = lowest[i - 1] * nr_prime[i];
}

int main() {
    precalc();
    inceput;
    for(int i = 1; i <= t; i++) {
        fin >> n >> k;
        if( lowest[k] > n )
            fout << 0 << "\n";
        else {
            auto x = lower_bound(how_many[k].begin(), how_many[k].end(), n);
            x--;
            fout << *x << "\n";
        }
    }
    sfarsit;
}