#include <iostream>
#include <fstream>
#include <cstdio>
using namespace std;
ofstream g("divprim.out");
int a[1000001],i,n,t,j,k,nd,ii;
int main()
{
    freopen("divprim.in","r",stdin);
    scanf("%d",&t);
    /*for(i=2;i<=1000000;i++)
    {
        if(a[i]==0)
        {
            for(j=i;j<=1000000;j=i+j)
            {
                a[j]++;
            }
        }
    }*/
    for(i=1;i<=500000;i++)
    {
        if(a[i]==0)
        {
            for(j=i;j<=500000;j=j+2*i+1)
            {
                a[j]++;
            }
        }
    }
    j=11;
    for(i=1;i<=t;i++)
    {
        scanf("%d" "%d",&n,&k);
        for(j=n;j>0&&nd!=k;j--)
        {
            ii=j;
            if(ii%2==0)
            {
                while(ii%2==0)
                {
                    ii=ii>>1;
                }
                nd=a[(ii-1)/2]+1;
            }
            else nd=a[(ii-1)/2];
        }
        if(j>0)
        {
            g<<j+1<<'\n';
        }
        else g<<0<<'\n';
    }

    return 0;
}