#include <fstream>
#include <algorithm>
#define NDIM 1000000

using namespace std;

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

int nr, n, d, i, t, nrdiv, k, st, dr, mid, j, mat[NDIM][8];

int v[NDIM + 2];


int main()
{
    for(i = 2;i <= NDIM; ++ i)
    {
        if(v[i] == 0)
        {
            int itin = i;
            for(int it = 1;it * itin <= NDIM;++ it)
            {
                ++ v[it * itin];
            }
        }
    }

    for(i = 2; i <= NDIM; ++ i)
    {
        for(j = 1; j <= 7; ++ j)
        {
            mat[i][j] = mat[i - 1][j];
        }
        mat[i][v[i]] = i;
    }

    f>>t;
    for(int o = 1;o <= t; ++ o)
    {
        f>>n>>k;
        g<<mat[n][k]<<'\n';;
    }
    return 0;
}