#include <bits/stdc++.h>

using namespace std;

const int M=1000000;
int v[M];

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

void ciur()
{
    v[0]=0;
    v[1]=0;
    for(int i=2; i<M; i++)
    {
        if(v[i]==0)
        {
            for(int j=i; j<M; j+=i) v[j]++;
        }
    }
}

int main()
{
    ciur();
    int t, n, k;
    in >> t;
    for(int i=0; i<t; i++)
    {
        in >> n >> k;
        while(n>1)
        {
            n--;
            if(v[n]==k) break;
        }
        if(n>1) out << n << '\n';
        else out << 0;
    }
    return 0;
}