#include <iostream>
#include <fstream>

using namespace std;

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

const int N = 1000000;

int ciur[N];
int mat[8][N];
int nrk[8];


int main()
{
    int t, d, i, n, k;
    in>>t;
    for( d = 2; d * d <= N; d++ ){
        if( ciur[d] == 0 ){
            for( i = d; i <= N; i+=d ){
                ciur[i]++;
            }
        }
    }
    for( d = 2; d <= N; d++ ){
        if( ciur[d] <= 7 && ciur[d] != 0 ){
            mat[ ciur[d] - 1 ][d] = d;
            nrk[ ciur[d] -1 ] = d;
        }
        for( i = 0; i < 8; i++ ){
            mat[i][d] = nrk[i];
        }

    }
    for( i = 0; i < t; i++ ){
       // cout<<" B";
        in>>n>>k;
        if( k == 0)
            out<<"1";
        else
            out<<mat[ k - 1 ][ n ]<<'\n';
    }
    return 0;
}