# include <fstream>
# include <cstdio>
using namespace std;
    char ci[ (1000000 >> 3) + 1];
	int v[ (1000000 >> 1) + 100], cnt, i, t, n, di;
	
	void ciur (){
		int i, j;
		for (i=4;i<=1000000;i+=2)
			ci[i/8]|=(1<<(i%8));
		i=1;
		v[++cnt]=2;
		while (i<=1000000){
			do{
				i+=2;
			}while (ci[i/8] & (1<<(i%8)));
			for (j=i*2;j<=1000000;j+=i) ci[j/8]|=(1<<(j%8));
			v[++cnt]=i;
		}
	}
	
	int check (int n){
	    int i, ret=0, cab;
		for (i=1;v[i]*v[i]<n;++i){
			if (n%v[i]==0){
    			++ret;
	    		cab=n/v[i];
 		    	if (  !(ci[cab/8] & (1<<(cab%8))) && v[i]!=cab ) 
			    	++ret;
			    //ret+= (!(ci[cab/8] & (1<<(cab%8))));
			}
		}
		if (v[i]*v[i]==n) ++ret;
		if (ret>=di)
		    return 1;
		return 0;
	}
	
	int cb (int in, int sf){
		int ret=0;
		while (in<=sf){
			int m= (in+sf) >> 1;
			if (check (m)){//salvezi si verif mai sus
				ret=m;
				//in=m+1;
			}
			in=m+1;//else sf=m-1;
		}
		return ret;
	}
	
    int main (){
		ifstream f ("divprim.in");
		freopen ("divprim.out", "w", stdout);
		ciur ();
		//for (i=1;i<=100;++i) printf ("%d ", v[i]);
		f>>t;
		for (;t;--t){
			f>>n>>di;
			printf ("%d\n", cb (1,n-1));
		}
		return 0;
	}