#include <bits/stdc++.h>
using namespace std;

int ciur[1000005];
vector<vector<int>>v;
int main()
{
    ifstream cin("divprim.in");
    ofstream cout("divprim.out");
    
    int m=7;
    for(int i=2; i<=1000000; i++)
    {
        if(ciur[i]==0)
        {
            for(int j=i; j<=1000000; j+=i)
            ciur[j]++;
        }
    }
    v.resize(m+1);
    for(int i=1; i<=1000000; i++)
    {
        if(ciur[i]==0)
        v[0].push_back(i);
        else if(ciur[i]==1)
        v[1].push_back(i);
        else if(ciur[i]==2)
        v[2].push_back(i);
        else if(ciur[i]==3)
        v[3].push_back(i);
        else if(ciur[i]==4)
        v[4].push_back(i);
        else if(ciur[i]==5)
        v[5].push_back(i);
        else if(ciur[i]==6)
        v[6].push_back(i);
        else if(ciur[i]==7)
        v[7].push_back(i);
    }
    int t, n, k, st, dr, mij, ans;
    cin>>t;
    for(int w=1; w<=t; w++)
    {
        cin>>n>>k;ans=0;
        st=0;dr=v[k].size()-1;
        while(st<=dr)
        {
            mij=(st+dr)/2;
            if(v[k][mij]>n)
            dr=mij-1;
            else
            {
                ans=v[k][mij];
                st=mij+1;
            }
        }
        cout<<ans<<'\n';
    }
    
    return 0;
}