#include<bits/stdc++.h>
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
int ciur[1000001];
vector<int>v[8];
int main()
{
    int t,n,k;
    for(int i=2;i<=1000000;i++)
        if(!ciur[i])
        {
            for(int j=i;j<=1000000;j+=i)
                ciur[j]++;
        }
    for(int i=0;i<=7;i++)
        v[i].push_back(0);
    for(int i=1;i<=1000000;i++)
        v[ciur[i]].push_back(i);
    fin>>t;
    while(t--)
    {
        fin>>n>>k;
        int st=0,dr=v[k].size()-1,mi,poz;
        while(st<=dr)
        {
             mi=(st+dr)/2;
             if(v[k][mi]>n)
                 dr=mi-1;
             else
             {
                 st=mi+1;
                 poz=mi;
             }
        }
        fout<<v[k][poz]<<"\n";
    }
}