#include <iostream>
#include <fstream>

//#define int long long

using namespace std;

int divizori[1000000+1];
int maxim[10][1000000+1];

signed main()
{
    freopen("divprim.in", "r", stdin);
    freopen("divprim.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    for (int i=2; i<=1000000; i++) {
        if (divizori[i]==0) {
            for (int j=i; j<=1000000; j+=i) {
                divizori[j]++;
            }
        }
    }

    int pozprec1=0;
    int pozprec2=0;
    int pozprec3=0;
    int pozprec4=0;
    int pozprec5=0;
    int pozprec6=0;
    int pozprec7=0;
    for (int i=1; i<=1000000; i++) {
        if (divizori[i]==1) {
            maxim[1][i]=i;
            pozprec1=i;
        }
        else maxim[1][i]=pozprec1;
        if (divizori[i]==2) {
            maxim[2][i]=i;
            pozprec2=i;
        }
        else maxim[2][i]=pozprec2;
        if (divizori[i]==3) {
            maxim[3][i]=i;
            pozprec3=i;
        }
        else maxim[3][i]=pozprec3;
        if (divizori[i]==4) {
            maxim[4][i]=i;
            pozprec4=i;
        }
        else maxim[4][i]=pozprec4;
        if (divizori[i]==5) {
            maxim[5][i]=i;
            pozprec5=i;
        }
        else maxim[5][i]=pozprec5;
        if (divizori[i]==6) {
            maxim[6][i]=i;
            pozprec6=i;
        }
        else maxim[6][i]=pozprec6;
        if (divizori[i]==7) {
            maxim[7][i]=i;
            pozprec7=i;
        }
        else maxim[7][i]=pozprec7;
    }

    int n;
    cin >> n;
    for (int i=1; i<=n; i++) {
        int x, div;
        cin >> x >> div;
        cout << maxim[div][x] << "\n";
    }
    return 0;
}