#include <iostream>
#include <cstdio>
using namespace std;

int ww[1000005];

void ciur()
{
    for(int i = 2; i <= 1000000; i += 2)
        ww[i] = 1;
    for(int i = 3; i <= 1000000; i += 2)
        if(!ww[i])
            for(int j = i; j <= 1000000; j += i)
                ww[j]++;
}

int main()
{
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    int t; cin >> t;

    ciur();
    for(int i = 1; i <= t; ++i)
    {
        int x, y; cin >> x >> y;
        bool ok = 1;
        for(int j = x; j > 0; --j)
            if(ww[j] == y)
            {
                cout << j << '\n';
                ok = 0;
                break;
            }
        if(ok)
            cout << 0 << '\n';
    }
    return 0;
}