#include<bits/stdc++.h>
using namespace std;
ifstream F("divprim.in");
ofstream G("divprim.out");
vector<int> v[8];
unsigned char b[1000001];
int n=1e6,i,t,k,j;
int main()
{
    for(i=2;i<=n;++b[i],i+=2);
    for(i=3;i<=n;i+=2)
        if(!b[i])
            for(j=i;j<=n;++b[j],j+=i);
    for(i=1;i<=n;v[b[i]].push_back(i),++i);
    for(F>>t;t--;F>>n>>k,G<<(v[k][0]>n?0:v[k][upper_bound(v[k].begin(),v[k].end(),n)-v[k].begin()-1])<<'\n');
    return 0;
}