#include <fstream>

using namespace std;
const int VM = 1000001;
int v[VM];
int main()
{
    ifstream cin("divprim.in");
    ofstream cout("divprim.out");
    for (int i = 2; i < VM; i++) {
      if (v[i] == 0) {
        for (int j = i; j < VM; j+= i) {
          v[j]++;
        }
      }
    }
    int t, n, k;
    cin >> t;
    for (int i = 0; i < t; i++)
    {
      cin >> n >> k;
      v[0] = k;
      int j = n;
      while (v[j] != k)
      {
        j--;
      }
      cout << j;
    }
    return 0;
}