#include <bits/stdc++.h>

using namespace std;
ifstream fin("transport.in");
ofstream fout("transport.out");
bitset<1000003> a;
int v[1000003];
vector<int> p[8];
int t,x,b;
int main()
{
    a[0]=a[1]=1;
    v[0]=v[1]=0;
    for (int i=2;i<=1000000;i++)
    {
        if (a[i]==0)
        {
            v[i]=1;
            for (int j=2*i;j<=1000000;j+=i)
                a[j]=1,v[j]++;
        }
    }
    for (int i=0;i<=1000000;i++)
        p[v[i]].push_back(i);
    fin>>t;
    while (t--)
    {
        fin>>x>>b;
        int poz=upper_bound(p[b].begin(),p[b].end(),x)-p[b].begin()-1;
        if (poz<0) fout<<0;
        else fout<<p[b][poz];
        fout<<'\n';
    }
    return 0;
}