#include <bits/stdc++.h>
using namespace std;
ifstream fin ( "divprim.in" );
ofstream fout ( "divprim.out" );
const int N = 1000000;
int n, x, y;
int ciur[N + 5];
int m[N + 5][10];
int main() {
    for ( int i = 2; i <= N; i++ ) {
        if ( !ciur[i] ) {
            for ( int j = i; j <= N; j += i )
                ciur[j]++;
        }

        if ( ciur[i] <= 7 )
            m[i][ciur[i]] = i;
    }

    for ( int i = 1; i <= 1000000; i++ ) {
        for ( int j = 1; j <= 7; j++ )
            if ( m[i][j] == 0 )
                m[i][j] = m[i - 1][j];
    }

     for ( int i = 1; i <= 1000000; i++ ) {
         for ( int j = 1; j <= 7; j++ )
             fout << m[i][j] << ' ';

         fout << endl;
     }
    fin >> n;

    for ( int i = 1; i <= n; i++ ) {
        fin >> x >> y;
        fout << m[x][y] << '\n';
    }

    return 0;
}