/*STAN Elisabeta
CN Andrei Saguna
cls 10
[email protected]*
problema "divizori primi"*/
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("divprim.in");
ofstream fout("divprim.out");
int main()
{
    int t,n,k,nrd=0;
    fin>>t;

    for(int i=0;i<t;i++){
        fin>>n>>k;
        for(int x=n;x>0;x--)
        {
            int nrx=2;
            if(x>2 || x<2 && x%2==0)
            {
                nrx+=2;
                nrd++;
            }
            for(int d=3;d*d<x;d++)
            {
                int nrj=2;
                if(x%d==0)
                {
                    nrx+=2;
                    if(d%2==0)
                        nrj+=2;
                    for(int j=3;j*j<d;j++)
                        if(d%j==0)
                            nrj+=2;
                }
                if(nrj==2)
                    nrd++;
            }
            if(nrd==k)
            {
                break;
                fout<<x<<endl;
            }
            if(x==1)
                fout<<0<<endl;
        }
    }

    return 0;
}