#include <stdio.h>
#define TMAX 100000
#define NMAX 1000000
#define KMAX 7
int liste[NMAX + 1], ciur[NMAX + 1], n[TMAX], k[TMAX], next[TMAX], rasp[TMAX], maxim[KMAX + 1];
int main() {
    FILE *fin, *fout;
    int t, i, j, d;
    for ( i = 0; i <= NMAX; i++ )
        liste[i] = -1;
    fin = fopen( "divprim.in", "r" );
    fscanf( fin, "%d", &t );
    for ( i = 0; i < t; i++ ) {
        fscanf( fin, "%d%d", &n[i], &k[i] );
        next[i] = liste[n[i]];
        liste[n[i]] = i;
    }
    fclose( fin );
    for ( i = 2; i <= NMAX; i++ ) {
        if ( ciur[i] == 0 ) {
            d = 0;
            for ( d = i; d <= NMAX; d += i ) {
                ciur[d]++;
            }
        }
        for ( j = 0; j <= KMAX; j++ ) {
            if ( ciur[i] == j )
                maxim[j] = i;
        }
        j = liste[i];
        while ( j != -1 ) {
            rasp[j] = maxim[k[j]];
            j = next[j];
        }
    }
    fout = fopen( "divprim.out", "w" );
    for ( i = 0; i < t; i++ )
        fprintf( fout, "%d\n", rasp[i] );
    fclose( fin );
    return 0;
}