#include <bits/stdc++.h>

using namespace std;

ifstream in("divprim.in");
ofstream out("divprim.out");

const int N=1000000;
bitset<1000001>ciur;
int i,j,d[1000001];
int main()
{
    for(i=2;i<=N;i+=2)
        d[i]++;
    for(i=3; i<=N; i+=2)
        if(ciur[i]==0)
        {
            d[i]++;
            for(j=2; j*i<=N; j++)
            {
                ciur[i*j]=1;
                d[i*j]++;
            }
        }
    int t;
    in>>t;
    while(t--)
    {
        int n,k;
        in>>n>>k;
        do
        {
            n--;
            if(d[n]==k)
                break;
        }while(n);
        out<<n<<"\n";
    }
    return 0;
}