#include <bits/stdc++.h>

using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
int t,i,j,n,k,ciur[1000000];
int main()
{
    fin>>t;
    for(i=2; i<=1000000; i+=2) ciur[i]++;
    for(i=3; i<1000000; i+=2)
    {
        if(ciur[i]==0)
        {
            for(j=i; j<=1000000; j+=i)
            {
                ciur[j]++;
            }
        }

    }
    for(i=1; i<=t; i++)
    {
        fin>>n>>k;
        for(j=n; j>0; j--) if(ciur[j]==k)
            {
                fout<<j<<'\n';
                break;
            }
            if(j==0) fout<<0<<'\n';

    }
    return 0;
}