#include<stdio.h>

const char in[]="divprim.in", out[]="divprim.out";
const unsigned N = 1000050;

unsigned a[8][N], n, k, T, v[N];

void ciur()
	{
	for(unsigned i = 2 ; i <= N ; ++i)
		if(!v[i])
			{
			a[1][++a[1][0]] = i;
			for( unsigned j = i + i ; j <= N ; j += i)
				++v[ j ];
			}
		else a[ v[ i ] ][ ++a[ v[ i ] ][ 0 ] ] = i;
}
unsigned caut(unsigned tar, unsigned lin)
    {       
		unsigned lo = 1, hi = a[lin][0], mid, sol = 0;
		for( ; lo <= hi ; )
        {
		mid = (lo +  hi) >> 1;
			if( a[ lin ][ mid ] <= tar )
				{
					sol = a[ lin ][ mid ];
					lo = mid + 1;
			}
			else if(a[ lin ][ mid ] > tar ) hi = mid - 1 ;
			}
		return sol;
		}
	
int main()
{
	freopen(in,"r",stdin);
	freopen(out,"w",stdout);
	scanf("%u", &T);
	ciur();
	for(; T-- ; )
	{
		scanf("%u%u", &n, &k);
		if(!k ) printf("1\n");
		else printf("%u\n",caut(n, k));
	}
	return 0;
}