#include <iostream>
#include <fstream>

using namespace std;

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

const int N = 1000050;

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


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

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