# include <fstream>
# include <cstdio>
# define  N  1000000
using namespace std;
	short dprim[N+1];
	int n, t, k, val, i, mi;
	int mat[8][1000001];
	
	void ciur (){
		int i, j;
		for (i=4;i<=N;i+=2){ 
			++dprim[i];
		}
		i=1;
		while (i<=N){
			do{
				i+=2;
			}while (dprim[i] && i<=N);
			for (j=(i << 1);j<=N;j+=i){
				++dprim[j];
			}
			++dprim[i];
		}
		dprim[2]=1;
	}
	
	int cb (int in, int sf, int find, int dprim[]){
		int ret=0;
		while (in<=sf){
			int m= (in+sf) >> 1;
			if (dprim[m]<find){//cauti mai sus
				ret=dprim[m];
				in=m+1;
			}
			else 
			if (dprim[m]>find) sf=m-1;
			else in=m+1;
		}
		return ret;
	}
	
    int main (){
		ifstream f ("divprim.in");
		freopen ("divprim.out", "w", stdout);
		ciur ();
		for (i=2;i<=N;++i){
			mat[dprim[i]][++mat[dprim[i]][0]]=i;
		}
		for (f>>t;t;--t){
			f>>n>>k;
			printf ("%d\n",cb (1, n, n, mat[k]));
		}
		return 0;
	}