#include <iostream>
#include <fstream>
 const int maxn=1000000;

using namespace std;

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

int m[15][2000000];
int freq[1000001];
bool ciur[1000001];
int pos[8];
int main()
{
    int n,t,k,i,j;
    freq[2]=1;
    i=4;
    while(i<=maxn)
    {
        freq[i]++;
        ciur[i]=1;
        i+=2;
    }
    for(i=3;i<maxn;i+=2)
    {
        if(ciur[i]==0)
        {
            freq[i]++;
            ciur[i]=1;
            j=2*i;
            while(j<=maxn)
            {
                freq[j]++;
                ciur[j]=1;
                j+=i;
            }
        }
    }
    for(i=1;i<=7;i++)
    {
        k=1;
        for(j=2;j<=maxn;j++)
        {
            if(freq[j]==i)
                m[i][k++]=j;
        }
        pos[i]=k-1;
    }

    int nr,d;
    int step,p;
     fin >> t;
    for(i=1;i<=t;i++)
    {
        fin >> nr >> d;

        step=1<<19;
        p=0;
        while(step>0)
        {
            if(step+p<=pos[d])
                if(m[d][step+p]<=nr)
                p+=step;
            step/=2;
        }
        fout << m[d][p]<< '\n';
    }

    return 0;
}