#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("divprim.in");
ofstream out("divprim.out");
const int nr=1000001;
vector <int> div[nr];
int v[nr];
void ciur()
{
    int i,j;
    for(i=2;i<=nr;i++)
    {
        while(v[i]!=0)
            i++;
        for(j=i;j<=nr;v[j]++,j+=i);
    }
	for(i=2;i<=nr;i++)
		div[v[i]].push_back(i);
}
int caut(int x,int k)
{
	int i=-1,pas=1<<19,n=div[k].size();
	while(pas!=0)
	{
		if(i+pas<n && div[k][pas+i]<=x)
			i+=pas;
		pas/=2;
	}
	return i;
}
int main()
{
    int t,x,k,n,i,j;
    ciur();
    in>>t;
    for(i=0;i<t;i++)
    {
        in>>x>>k;
        n=caut(x,k);
		if(n==-1)
			out<<0<<"\n";
		else
			out<<div[k][n]<<"\n";
    }
    return 0;
}