#include <iostream>
#include <fstream>
#define MAX 1000000
int ciur[MAX + 1];
int a[8][MAX + 1];
using namespace std;

int main(){

    int i, j, d, n, k, t;

    ifstream fin( "divprim.in" );
    ofstream fout( "divprim.out" );
    ///ciur
    ciur[1] = 1;
    for ( d = 2; d <= MAX; d++ )
        if ( ciur[d] == 0 )
            for ( i = d; i <= MAX; i += d )
                ciur[i]++;
    ///
    for ( i = 1; i <= MAX; i++ )
        a[ciur[i]][i] = 1;
    for ( i = 1; i <= 7; i++ )
        for ( j = 1; j <= MAX; j++ )
            if ( a[i][j] )
                a[i][j] = j;
            else
                a[i][j] = a[i][j - 1];
    fin >> t;
    for ( i = 1; i <= t; i++ ){
        fin >> n >> k;
        fout << a[k][n] << "\n";
    }

    fin.close();
    fout.close();

    return 0;
}