#include <cstdio>
#include <vector>
#define NMAX 1000000
using namespace std;

int V[1000001];
int N, T, K;

vector<int> con[8];

void ciur()
{
    for(int i = 2; i <= NMAX; i++)
    {
        V[i] = 0;
    }

    for(int i = 2; i <= NMAX; i += 2)
    {
        V[i]++;
    }

    for(int i = 3; i <= NMAX; i += 2)
    {
        if(V[i] == 0)
        {
            for(int j = i; j <= NMAX; j += i)
            {
                V[j]++;
            }
        }
    }
}

void pre()
{
    for(int i = 0; i <= NMAX; i++)
    {
        if(V[i] <= 7)
            con[V[i]].push_back(i);
    }
}

int find()
{
    int l = 0;
    int r = con[K].size() - 1;
    int sol = 0;
    if(con[K].size() == 0)
    {
        return 0;
    }
    while(l < r)
    {
        int mid = (l+r)/2;
        //printf("%d\n", mid);
        if(con[K][mid] > N)
        {
            r = mid - 1;
        }
        else
        {
            sol = con[K][mid];
            l = mid + 1;
        }
    }
    return sol;
}

int main()
{
    ciur();
    pre();
    freopen("divprim.in", "r", stdin);
    freopen("divprim.out", "w", stdout);
    scanf("%d", &T);
    for(int i = 0; i < T; i++)
    {
        scanf("%d %d", &N, &K);
        printf("%d\n", find());
    }
    return 0;
}