#include<stdio.h>
#include<cstring>
#include<iostream>
#include<fstream>

using namespace std; 	
#define maxn 1000001

int v[maxn], nrdiv[maxn];
int ans[maxn][8];

void find_divizori( int max) {
	
	for( int i = 2; i <= max; ++i)
		if(v[i] == 0)
			for( int j = 1; j * 1ll * i <= max; ++j){
				v[i*j] = i;
			}
	
	nrdiv[1] = 0;
	for( int i = 2; i <= max; ++i) {
		int value = i, nr = 0, last_div = -1000;
		while( value != 1) {
			if( v[value] != last_div) {
					nr++;
				last_div = v[value];
			}
			value /= v[value];
		}
		nrdiv[i] = nr;
	}
	int last[8];
	memset(last, 0, sizeof(last));
	for( int i = 0; i<= max; i++) {
		if( nrdiv[i] <= 7)
			last[ nrdiv[i]] = i;
		for(int ii = 7; ii >= 1; ii--)
			ans[i][ii] = last[ii];
	}
	
}

int main() {
	
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	find_divizori(1000000);
	int n,a,b;
   
    scanf("%d",&n);
 
    for(int i=1;i<=n;i++)
    {
		int a, b;
        scanf("%d%d",&a,&b);
        printf("%d\n",ans[a][b]);
    }
	return 0;
}