#include<bits/stdc++.h>
using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");
int t,n,k,nr;
int v[1000002];
bitset<1000002>p;
int v1[8][1000002];
int c[8];
void ciur()
{
    v[2]=1;
    for(int i=4;i<=1000000;i+=2)
        p[i]=v[i]=1;
    for(int i=3;i<=1000000;i+=2)
        if(p[i]==0)
        {
            v[i]=1;
            for(int j=i+i;j<=1000000;v[j]++,j+=i)
                p[j]=1;
        }
    for(int i=2;i<=1000000;++i)
    {
        c[v[i]]++;
        v1[v[i]][c[v[i]]]=i;
    }
}
int main()
{
    f>>t;
    ciur();
    for(int i=1;i<=t;i++)
    {
        f>>n>>k;
        if(n<v1[k][1])
            g<<0<<'\n';
        else
        {
            int b=1;
            int e=c[k];
            while(b<=e)
            {
                int m=(b+e)/2;
                if(v1[k][m]<=n && v1[k][m+1]>n){
                    g<<v1[k][m]<<'\n';
                    break;
                }
                else
                    if(v1[k][m]>n)
                        e=m-1;
                    else
                        b=m+1;
            }
        }
    }
    return 0;
}