#include <bits/stdc++.h>
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
int t, n, k;
int nrd[1000002];
void ciur()
{
    int i, j;
    for(i=2; i<=1000000; i+=2)
        nrd[i]++;
    for(i=3; i<=1000000; i+=2)
        if(!nrd[i])
            for(j=i; j<=1000000; j+=i)
                nrd[j]++;
}
int main()
{
    int i, j;
    bool ok;
    ciur();
    fin>>t;
    for(i=1; i<=t; i++)
    {
        ok=0;
        fin>>n>>k;
        if(k==0)
            {
                fout<<0<<'\n';
                ok=1;
            }
        else
            for(j=n; j>=2; j--)
                    if(nrd[j]==k)
                        {
                            ok=1;
                            fout<<j<<'\n';
                            break;
                        }
        if(!ok)
            fout<<0<<'\n';
    }
    return 0;
}