/**          _-_.
        _-',^. `-_.
    ._-' ,'   `.   `-_
    !`-_._________`-':::
    !   /\        /\::::
    ;  /  \      /..\:::
    ! /    \    /....\::
    !/      \  /......\:
    ;--.___. \/_.__.--;;
    '-_    `:!;;;;;;;'
        `-_, :!;;;''
            `-!'                         */

#include <fstream>
using namespace std;

const int N = 1000000;
const int IND = 999999;
int ciur[N];
int mat[8][N];

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

int main()
{
    int t, n, i, j, k, indice, st, dr, mij;
    ciur[1] = 0;
    for(i = 2; i <= N; i++){
        if(ciur[i] == 0){
            for(j = i; j <= N; j += i){
                ciur[j]++;
            }
        }
    }
    for(i = 1; i <= 7; i++){
        indice = 0;
        for(j = 1; j <= N; j++){
            if(ciur[j] == i){
                mat[i][indice] = j;
                indice++;
            }
            mat[i][IND] = indice;
        }
    }

    fin >> t;
    for(i = 0; i < t; i++){
        fin >> n >> k;
        st = 0;
        dr = mat[k][IND];
        while(dr - st > 1){
            mij = (st + dr) / 2;
            if(mat[k][mij] > n){
                dr = mij;
            }else{
                st = mij;
            }
        }
        if(st == 0 && mat[k][st] > n){
            fout << 0 << endl;
        }else{
            fout << mat[k][st] << endl;
        }
    }
    fin.close(); fout.close();
    return 0;
}