// Craciun Catalin
//  Infoarena
//   DivPrim

#include <iostream>
#include <ctime>
#include <cmath>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <iomanip>

#define DBG 1
#define NMax 1000005

using namespace std;

ifstream f("divprim.in");
ofstream g("divprim.out");

int A[NMax]; // A[i] - numarul de divizori primi pe care ii are i

void ciur() {

      memset(A, 0, sizeof(A));
      for (int i=2;i<=NMax - 5;i++) {
	    if (A[i] == 0) {
		  for (int j=i+i;j<=NMax - 5;j+=i)
			A[j]++;
	    }
      }
}

int n;
int main() {
	
#ifdef DBG
	float one = clock();
#endif //DBG

	ciur();
	f>>n;
	for (int i=1;i<=n;i++) {
	      int x, div;
	      bool printed = false;
	      f>>x>>div;
	      
	      while (x) {
		    if (A[x] == div) { 
			  g<<x<<'\n';
			  printed = true;
			  break;
		    } else
			  x--;
	      }

	      if (!printed)
		g<<0<<'\n';
	}
	
#ifdef DBG
	cout<<"\n\nTimpul in care s-a efectuat executia este "<<fixed<<setprecision(8)<<(clock()-one)/CLOCKS_PER_SEC;
#endif // DBG
	
	return 0;
}