#include <bits/stdc++.h>
using namespace std;
 
ifstream fin("divprim.in");
ofstream fout("divprim.out");
 
int t,n,k;
int ciur[1000001];
pair<int,int> a[1000001];
 
void fa_ciur() {
 
    for (int i = 2; i<=10; i++) {
        if (ciur[i] == 0) {
            ciur[i] = 1;
            for (int j = i*2; j<=10; j+=i) {
                ciur[j]++;
               // cout << j << endl;
            }
        }
    }
 
  //  for (int i = 1; i<=10; i++) {
  //      cout << ciur[i] << " ";
 //   }
}
 
int cautbin(int x) {
 
    int st = 1;
    int dr = n;
    int poz = 0;
 
    while (st <= dr) {
        int mid = (st+dr)/2;
        if (a[mid].first < x) {
            st = mid+1;
        } else if (a[mid].first > x) {
            dr = mid-1;
        } else {
            poz = mid;
            st = mid+1;
        }
    }
 
    return poz;
}
 
 
void rezolvare(int n, int k) {
 
    for (int i = 1; i<=n; i++) {
        a[i].first = ciur[i];
        a[i].second = i;
    }
 
    sort(a+1, a+n+1);
 
  //  for (int i = 1; i<=n; i++) {
   //     cout << a[i].first << " " << a[i].second << endl;
    //}
 
   // cout << cautbin(k) << endl;
 
    fout << a[cautbin(k)].second << endl;
}
 
int main() {
 
    fa_ciur();
 
    fin >> t;
 
    for (int i = 1; i<=t; i++) {
        fin >> n >> k;
        rezolvare(n,k);
    }
 
    return 0;
}