#include <fstream>
using namespace std;
ifstream cin("divprim.in");
ofstream cout("divprim.out");

const int N=1000001;
const int M=380000;

char c[N];

int a[8][M];

void ciur(int n)
{
	int maxx=0,i,j,r=0;
	for(i=2;i<=n;i++)
		if(c[i]==0)
			for(j=i;j<=n;j=j+i)
				c[j]=c[j]+1;
	//a[i][j]=al j-lea nr cu i div primi
	//a[i][0]=cate numere cu i div primi sunt
	for(i=1;i<=n;i++)
		a[  c[i]  ][ ++a[ c[i] ] [0] ] = i;
}

/*
int numar(int n,int k)//returneaza cel mai mare nr mai mic sau egal cu n, avand k divizori
{
	for(int i=n ; i>=1 ; --i)
		if(c[i] == k)
			return i;
	return 0;
}
*/

int numar(int n,int k)
{
	int st=1,dr=a[k][0],mid;
	while(st!=dr)
	{
		mid=(st+dr+1)/2;
		if(n>=a[k][mid])
			st=mid;
		else
			dr=mid-1;
	}
	if(a[k][st]>n)
	{
		if(st==1)
			return 0;
		return a[k][st-1];
	}
	return a[k][st];
}
int main()
{
	int t,n,k,i,j,r;
	cin>>t;
	ciur(N-1);
	for(i=1;i<=t;i++)
	{
		r=0;
		cin>>n;
		cin>>k;
		cout<<numar(n,k)<<"\n";
		/*
		if(k==1)
			k=0;
		for(j=n;j>=2;j=j-1)
			if(c[j]==k)
			{
				cout<<j<<"\n";
				j=0;
				r=1;
			}
		if(r==0)
			cout<<"0 \n";
		*/
	}
	return 0;
}