#include<stdio.h>
#define N 1000020
char v[N];
int a[8][500000];
void ciur(){
	int i,j;
	v[0]=v[1]=0;
	for(j=2;j<N;j+=2)
		++v[j];
	//--k;
	for(i=3;i<N;i+=2)
		if(!v[i]){
			//--k;
			//if(!k)
				//return i;
			for(j=i;j<N+1;j+=i)
				++v[j];
		}
	//return 0;
}
inline void adaug(int linie,int x){
	a[linie][++a[linie][0]]=x;
}
void complet_mat(){
	int i;
	for(i=1;i<N;++i)
		adaug(v[i],i);
}
int cauta(int n,int k){
	/*
	for (int i=1;i<n+1;++i)
		printf("%d %d\n",i,v[i]);
	return 0;
	*/
	int p,u,m;
	p=1;u=a[k][0];
	while (p<u){
		m=(p+u)/2;
		if(n<=a[k][m])
			u=m;
		else
			p=m+1;
	}
	if(a[k][p]>n)
		return p-1;
	return p;
}
int main(){
	int n,k,t,i,r;
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	ciur();
	complet_mat();
	scanf("%d",&t);
	for (i=0;i<t;++i){
		scanf("%d%d",&n,&k);
		r=cauta(n,k);
		if(r==0)
			printf("%d\n",r);
		else
			printf("%d\n",a[k][r]);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}