//'If opportunity doesn't knock, build a door'
//Milton Berle
#include <iostream>
#include <fstream>

using namespace std;
constexpr int NX = 10e6+3;
constexpr int PN = 10;
int n, k, t;
int C[NX]= {}; //ciurul meu
int M[PN][NX];
void ciur() //calculeaza de la 1 la NX nr de div primi al fiec nr
{
    for(int i=2; i<=NX; ++i)
    {
        if(C[i]==0)
        {
            C[i]=1;
            for(int j=2*i; j<=NX; j+=i)
            {
                C[j]++;
            }
        }

    }
}
void solve() //face matrice cu cate nr sunt pe poz 0 a fiec linii
{
    M[0][1]=1;
    for(int i=2; i<=NX; ++i)
    {
        M[C[i]][0]++;
        int cateNr=M[C[i]][0];
        M[C[i]][cateNr]=i;
    }
}

int cautareBinara(int linie, int st, int dr, int x)
{
    if(M[linie][1]>x) return -1;
    int mij;
    while(st<dr)
    {
        mij=(st+dr)/2;
        if(M[linie][mij]>x)
            dr=mij-1;
        else st=mij+1;
    }
    if(M[linie][st]>x) st--;
    return st;
}
int main()
{
    ifstream fin("divprim.in");
    ofstream fout("divprim.out");
    ciur();
    solve();
    fin>>t;
    for(int i=1; i<=t; ++i)
    {
    fin>>n>>k;
    int x=cautareBinara(k, 1, M[k][0], n);
    if(x==-1)
        fout<<0;
    else
        fout<<M[k][x]<<endl;
    }
    return 0;
}