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

#include <fstream>
using namespace std;

const int N = 1000006;
const int IND = 1000000;
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] <= 7){
            mat[ciur[i]][mat[ciur[i]][IND]] = i;
            mat[ciur[i]][IND]++;
        }
        if(ciur[i] == 0){
            for(j = i; j <= N; j += i){
                ciur[j]++;
            }
        }
    }

    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;
        }
    }
    return 0;
}