#include <stdio.h>
#define N 1000000
using namespace std;
FILE *fin ,*fout;
int ramas[8];
   int i ,j ;
    char v[1000001];
    int a[1000001];
    int pun ,aux ,sunt[8][1000001] ,n ,st ,b;
int main()
{

    fin = fopen("divprim.in" ,"r");
    fout = fopen("divprim.out" ,"w");
    for(i=2;i<=N;i++)
    {
        if(v[i]==0)
        {
            a[i]=1;
            for(j=2*i;j<=N;j+=i)
            {
                a[j]++;
                v[j]=1;
            }
        }
    }
    for(i=1;i<=N;i++)
    {
        ramas[a[i]]++;
        sunt[a[i]][ramas[a[i]]]=i;
    }
    for(i=1;i<=N;i++)
    {
        for(j=1;j<=7;j++)
        {
            if(sunt[j][i]==0) sunt[j][i]=1000001;
        }
    }
    fscanf(fin ,"%d" ,&n);
    for(i=1;i<=n;i++)
    {
        fscanf(fin ,"%d%d" ,&st ,&b);
            aux=0;
            pun=2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2;
            while(pun+aux<=1000000 && pun>0)
        {
            if(pun+aux<1000000 && sunt[b][pun+aux]<=st)
            {
                aux+=pun;
            }
            pun/=2;
        }
        if(sunt[b][aux]>st) fprintf(fout ,"0\n");
        else fprintf(fout ,"%d\n" , sunt[b][aux]);
    }
    return 0;
}