#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;
}