#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream in("divprim.in");
ofstream out("divprim.out");

pair<int, int8_t> v[1000001];
int t,n,k;

int main()
{
    in>>t;
    v[0].first=0;
    v[1].first=1;
    for(int i = 2; i<=1000000; i++)
    {
        v[i].first=i;
        if(v[i].second==0)
        {
            for(int j = 1; j<=1000000/i; j++)
            {
                v[i*j].second++;
            }
        }
    }
    sort(v+1,v+1000001,[](const pair<int, int8_t>& left, const pair<int, int8_t>& right)
    {
        return left.second!=right.second ? left.second<right.second : left.first<right.first;
    });
    for(int i = 1; i<=t; i++)
    {
        in>>n>>k;
        int initPos = find_if(v+1,v+1000001,[k](pair<int, int8_t> x)
        {
            return x.second==k;
        })-v;
        for(int pos = initPos; ; pos++)
        {
            if(v[pos].second==k && v[pos].first<=n && (v[pos+1].first>n || v[pos+1].second!=k))
            {
                out<<v[pos].first<<'\n';
                break;
            }
            else if(v[pos].second>k)
            {
                out<<0<<'\n';
                break;
            }
        }
    }
    return 0;
}