#include <iostream>
#include <fstream>
using namespace std;
ifstream f ( "divprim.in" );
ofstream g ( "divprim.out" );
const int NMAX = 1000000;
short nd[NMAX + 1];
int ans[NMAX + 1][8];
int last[20];
void ciur ( int n )
{
    for ( int i = 2; i <= n; i+=2 )
        nd[i] = 1;

    for ( int i = 3; i * i <= n; i++ )
        if ( nd[i] == 0 )
            for ( int j = i; j <= n; j += i )
                nd[j]++;

    for ( int i = 2; i <= n; i++ )
        if ( nd[i] == 0 )
            for ( int j = i; j <= n; j += i )
                nd[j]++;

    for ( int i = 2; i <= n; i++ )
    {
        last[nd[i]] = i;

        for ( int j = 1; j <= 7; j++ )
            ans[i][j] = last[j];
    }
}
int main()
{
    int T, x, ct;
    ciur(NMAX);
    f >> T;
    while ( T-- )
    {
        f >> x >> ct;
        g << ans[x][ct] << '\n';
    }

    return 0;
}