#include <iostream>
#include <fstream>

using namespace std;
int rez[100005];
int main()
{
    ifstream cin("divprim.in");
    ofstream cout("divprim.out");
    int nr;
    cin>>nr;
    for(int i=0; i<nr; i++)
    {
        int n,k,cnt,div,ok=0,cntfinal=0,verif=0;
        cin>>n>>k;
        cnt=n+1;
        while(cnt>0)
        {
            cnt--;
            for(int i=2; i<cnt; i++)
            {
                if(cnt%i==0)
                {
                    div=i;
                    for(int j=2; j<div; j++)
                    {
                        if(div%j==0 && div!=j)
                        {
                            ok=1;
                            break;
                        }
                    }
                    if(ok==0)
                        cntfinal++;
                    ok=0;
                }
            }
            if(cntfinal==k)
            {
                rez[i]=cnt;
                verif=1;
                break;
            }
            cntfinal=0;
        }
        if(verif==0)
           rez[i]=0;
        verif=0;
    }

    for(int i=0;i<nr;i++)
        cout<<rez[i]<<'\n';

    return 0;
}