#include<stdio.h>

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

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

void ciur()
	{a[0][0] = a[0][1] = 1;
	for(int i = 2 ; i <= N ; ++i)
		if(!v[i])
		{
		a[1][++a[1][0]] = i;
		for( int 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 caut(int nr, int lin)
	{
		int lo = 1, hi = a[lin][0], mid, sol = 0;
		for(; lo <= hi; )
		{mid = (lo + hi) >> 2;
			if(a[lin][mid
			
	*/		
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;
}