# include <fstream>
# include <cstdio>
# define  N  1000000
using namespace std;
    char v[ (N >> 3) + 2 ];
	short dprim[N+1];
	int n, t, k, poz[N+1], val, i, mi;
	int mat[8][N+1];
	
	void ciur (){
		int i, j;
		poz[1]=1;
		poz[2]=2;
		for (i=4;i<=N;i+=2){ 
			v[i/8]|=(1<<(i%8));
			++dprim[i];
			poz[i]=i;
		}
		i=1;
		while (i<=N){
			do{
				i+=2;
				poz[i]=i;
			}while ( (v[i/8] & (1<<(i%8))) && i<=N);
			for (j=(i << 1);j<=N;j+=i){
				poz[j]=j;
				v[j/8]|=(1<<(j%8));
				++dprim[j];
			}
			poz[i]=i;
		}
	}
	
	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]-1][++mat[dprim[i]-1][0]]=i;
		}
		for (f>>t;t;--t){
			f>>n>>k;
			printf ("%d\n",cb (1, n, n, mat[k-1]));
		}
		return 0;
	}