#include<stdio.h>

const char in[]="divprim.in", out[]="divprim.out";
const int N = 10000005;

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

void ciur()
	{a[0][0] = a[0][1] = 1;
	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;
}
int caut(int tar, int lin)
    {       
		int lo = 1, hi = tar, mid, sol = 0;
		for( ; lo <= hi ; )
        {
		mid = lo + ( hi - lo ) / 2;
			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("%d", &T);
	ciur();
	for(; T-- ; )
	{
		scanf("%d%d", &n, &k);
		printf("%d\n",caut(n, k));
	}
	return 0;
}