#include<fstream>
#include<vector>
using namespace std;
ifstream in ("divprim.in" );
ofstream out("divprim.out");
int mid,st,dr,n,k,t,i,j,alfa;
pair<int,int>hz[1000005];
vector<int>dp[1501];
int main(){
    hz[0].first = 1;
    hz[0].second = 0;
    hz[1].first = 1;
    hz[1].second = 0;
    for( i = 2; i <= 1000000; i ++ ){
        if( hz[i].first == 0 ){
            hz[i].second++;
            for( j = i + i; j <= 1000000; j += i ){
                hz[j].first = 1;
                hz[j].second ++;
            }
        }
    }
    for( i = 0; i <= 1000000; i ++ ){
        dp[hz[i].second].push_back(i);
    }
    in >> t;
    for( i = 1; i <= t; i ++ ){
        in >> n >> k;
        for( st = 0, dr = dp[k].size()-1; st <= dr; ){
            mid = ( st + dr ) >> 1;
            if( dp[k][mid] <= n ){
                st = mid + 1;
                alfa = dp[k][mid];
            }
            else{
                dr = mid - 1;
            }
        }
        if( dp[k].empty() == 0 && dp[k][dr] < n )
            out<<alfa<<"\n";
        else{
            out<<0<<"\n";
        }
    }
    return 0;
}