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


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;
	cin>>n;
	for( int i = 1; i <= n; ++i){
		int a, b;
		cin>>a>>b;
		cout<<ans[a][b]<<endl;
	}
	return 0;
}