#include <iostream>
#include <fstream>

using namespace std;

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

/*int nr[1000003];

int main()
{
    int t, k = 0, n, i, j, l, nrdiv;
    int ciur[79000];
    for(i = 2; i < 1000000; i++){
        if(nr[i] == 0){
            for(j = 2; j <= 1000000 / i; j++)
                nr[j * i] = 1;
            ciur[k++] = i;
            }
        }
    fin>>t;
    for(i = 0; i < t; i++){
        fin>>n>>k;
        for(j = n; j > 1; j--){
            nrdiv = 0;
            for(l = 0; ciur[l] <= j && nrdiv <= k; l++){
                if(j % ciur[l] == 0)
                    nrdiv++;
                }
            if(nrdiv == k){
                fout<<j<<"\n";
                break;
                }
            }
        if(j == 1)
            fout<<0<<"\n";
        }
}
*/

int ciur[1000003], nrdiv[1000003], sol[1000003][7];

int main(){
    int i, j;
    for(i = 2; i * i <= 1000000; i++){
        if(!ciur[i]){
            for(j = i * i; j <= 1000000; j += i)
                ciur[j] = 1;
            }
        }
    for(i = 2; i < 1000000; i++){
        if(!ciur[i]){
            for(j = i; j <= 1000000; j += i)
                nrdiv[j]++;
            }
        }
    for(i = 1; i <= 1000000; i++){
        for(j = 1; j <= 7; j++){
            if(nrdiv[i] == j)
                sol[i][j] = i;
            else sol[i][j] = sol[i - 1][j];
            }
        }

    int n, t, k;
    fin>>t;
    while(t--){
        fin>>n>>k;
        fout<<sol[n][k]<<"\n";
        }
    }