#include<bits/stdc++.h>
using namespace std;

#define int long long

int T,k,m;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>T;
    // T=10;
    while(T--)
    {
        cin>>k>>m;
        // k=999999999999999999,m=100;
        int nk=(k>>14)<<14;
        int ans=-1;
        for(int i=0;i<(1<<14);i++)
        {
            int n=i+nk;
            if(!n)
                continue;
            int c=m,f=-1;
            for(int j=n+1;;j++)
            {
                if(__gcd(j,n)==1)
                    c--;
                if(!c)
                {
                    f=j;
                    break;
                }
            }
            if((((f-n)^n))==k)
            {
                ans=n;
                break;
            }
        }
        cout<<ans<<"\n";
    }
}