#include <bits/stdc++.h>

using namespace std;
ifstream fin ("divprim.in");
ofstream fout ("divprim.out");
#define N 1000000
int t,k,n,c[1000002];
vector <vector<int>> M;
int main()
{
    fin>>t;
    for(int i=2;i<=N;i++)
    {
        if(c[i]==0)
        {
            for(int j=i;j<=N;j+=i)
            {
                c[j]++;
            }
        }
    }
    for(int i=0;i<=7;i++)
    {
        M.push_back({});
    }

    for(int i=1;i<=N;i++)
    {
        if(c[i]<=7)
        {
            M[c[i]].push_back(i);
        }
    }
    for(int j=1;j<=t;j++)
    {
        int nr=-1;
        fin>>n>>k;
        int st=0,dr=M[k].size()-1;
        if(M[k][0]>n)
            nr=0;
        else
        {
            while(st<=dr)
            {
                int mij=(st+dr)/2;
                if(M[k][mij]<=n)
                {
                    nr=M[k][mij];
                    st=mij+1;
                }
                else
                {
                    dr=mij-1;
                }
            }
        }
        fout<<nr<<"\n";
    }
    return 0;
}