#include <iostream>
#include <fstream>
using namespace std;
ifstream in("divprim.in");
ofstream out("divprim.out");

int n, t, k, v[1000005], i, j, rs, mat[8][1000005];
bool este[1000005];

void ciur()
{
    for(i=2; i<=1000000; ++i)
    {
        if(este[i]==0)
        {
            for(j=i; j<=1000000; j+=i)
            {
                ++v[j];
                este[j]=1;
            }
        }
    }
    for(i=1; i<=7; ++i)
    {
        mat[i][1]=0;
    }
    for(int i=2; i<=1000000; ++i)
    {
        mat[v[i]][i]=i;
        for(int j=1; j<8; ++j)
        {
            if(j!=v[i])
            {
                mat[j][i]=mat[j][i-1];
            }
        }
      /* for(i=1; i<8; ++i)
        {
            cout<<mat[j][i]<<" ";
        }
        cout<<'\n';*/
    }
}


int main()
{
    ciur();
   /* for(i=1; i<=100; ++i)
    {
        out<<i<<" "<<v[i]<<'\n';
    }*/
    in>>t;
    while(t>0)
    {
        in>>n>>k;
        out<<mat[k][n]<<'\n';
        --t;
    }
    return 0;
}