#include <fstream>
using namespace std;
ifstream cin("divprim.in");
ofstream cout("divprim.out");
const int NMAX = 1000000;
int n, sol[NMAX + 1][8], v[NMAX + 1];

int main(int argc, const char * argv[]) {
    v[1] = 1;
    
    for(int i=2; i <= NMAX; i++)
    {
        if(v[i] == 0)
        {
            for(int j=i; j<=NMAX; j+=i)
                v[j]++;
        }
    }
    
    for(int i=1; i<=NMAX; i++)
    {
        for(int j=1; j<=7; j++)
            sol[i][j] = sol[i-1][j];
            
        sol[i][v[i]] = i;
    }
    
    cin>>n;
    
    for(int i=1; i<=n; i++)
    {
        int nr, k;
        cin>>nr>>k;
        cout<<sol[nr][k]<<'\n';
    }
    return 0;
}