#include <fstream>
#include <vector>
using namespace std;
ifstream cin("divprim.in");
ofstream cout("divprim.out");
vector<int> a[8];
int ciur[1000001];
int main() {
        int n,t,i,j,k;
        for(int i=0;i<=7;i++)
                a[i].push_back(0);
        for(i=2; i<=1000000; i++)
                if(ciur[i]==0) {
                        ciur[i]=1;
                        for(j=2*i; j<=1000000; j+=i)
                                ciur[j]++;
                }
        for(i=1; i<=1000000; i++)
                a[ciur[i]].push_back(i);
        int st,dr,m,pp;
        cin>>t;
        for(i=1; i<=t; i++) {
                cin>>n>>k;
                st=1;
                dr=a[k].size();
                pp=-1;
                while(st<=dr&&pp==-1) {
                        m=(st+dr)/2;
                        if(n==a[k][m])
                                pp=n;
                        else {
                                if(n<a[k][m])
                                        dr=m-1;
                                else
                                        st=m+1;
                        }
                }
                if(pp==-1)
                        pp=a[k][dr];
                cout<<pp<<'\n';
        }
        return 0;
}