#include <fstream>
using namespace std;
ifstream in("divprim.in");
ofstream out("divprim.out");
const int N=1000000;
int cate[N+1],dp[N+1][8];
int main()
{
    int t,n,k,i,j;
    in>>t;
    for(i=2; i<=N; i++)
        if(!cate[i])
            for(j=i; j<=N; j+=i)
                cate[j]++;
    for(i=0; i<=N; i++)
    {
        for(j=1; j<=7; j++)
            dp[i][j]=dp[i-1][j];
        dp[i][cate[i]]=i;
    }
    for(i=1; i<=t; i++)
    {
        in>>n>>k;
        out<<dp[n][k]<<'\n';
    }
    return 0;
}