#include <fstream>
#include <bitset>
#include <iostream>
using namespace std;

int T;

pair<int, int> Q[100001];
int dp[1000001][8];
int Maxa, Maxb;

void read() {
    int i;
    ifstream f("divprim.in");
    f >> T;
    for (i = 1; i <= T; i++) {
        f >> Q[i].first >> Q[i].second;
        if (Q[i].first > Maxa)
            Maxa = Q[i].first;
        if (Q[i].second > Maxb)
            Maxb = Q[i].second;
    }
    f.close();
}

bitset<1501> e;
int primes[191], lung;

void Ciur() {
    int i, j;
    e[0] = e[1] = 1;
    for (i = 2; i * i <= 1500; i++)
        if (!e[i])
            for (j = 2; j * i <= 1500; j++)
                e[i * j] = 1;
    for (i = 2; i <= 1500; i++)
        if (!e[i])
            primes[lung++] = i;
}

void solve() {
    int i, d, k, x, j;
    Ciur();
    for (i = 1; i <= Maxa; i++) {
        x = i, k = 0;
        for (d = 0; primes[d] * primes[d] <= x; d++) {
            if (x % primes[d] != 0)
                continue;
            k++;
            while (x % primes[d] == 0) 
                x /= primes[d];
        }
        if (x > 1)
            k++;
        dp[i][k] = i;
        for (j = 1; j <= 7; j++)
            dp[i][j] = max(dp[i][j], dp[i - 1][j]);
    }
}

void output() {
    int i;
    ofstream g("divprim.out");
    for (i = 1; i <= T; i++)
        g << dp[Q[i].first][Q[i].second] << '\n';
    g.close();
}

int main() {
    read();
    solve();
    output();
    return 0;
}