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

using isize = size_t;
using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
using f64 = long double;
using p2 = pair<i64, i64>;
using el = tuple<i64, i64, i64>;
using mint = atcoder::modint998244353;

void _main();
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(3);
  _main();
}

i32 pow(i32 x, i32 n) {
  i32 res = 1;
  i32 a = x;
  while (n > 0) {
    if (n & 1) res *= a;
    a *= a;
    n >>= 1;
  }
  return res;
}

void _main() {
  i64 t;
  cin >> t;
  for (;t--;) {
    i64 r, c;
    cin >> r >> c;
    c--;
    i64 ans = 0;
    i64 i = 1, j = 0;
    while (j < c) {
      ans += 1ll << j;
      i += 1ll << j;
      j++;
      assert(i / (1ll << j) % 2 == 1);
    }
    while ((i >> j) != (r >> j)) {
      assert((i >> j) < (r >> j));
      ans += 1ll << j;
      i += 1ll << j;
      j++;
      assert(i / (1ll << j) % 2 == 1);
    }
      // cout << i << " " << j << "  " << r << " " << c << " " << ans << "!\n";
    while (c < j) {
      bool ok = false;
      for (i64 k = c; k <= j; k++) {
        if (!(r >> k & 1)) {
          ok = true;
        }
      }
      if (ok) {
        if (r / (1ll << (c + 1)) % 2 == 0) {
          i64 x = r >> c << c;
          i64 nr = x + (1ll << c);
          c++;
          ans += nr - r;
          r = nr;
        } else {
          i64 nr = min(r + 1, (((r >> (c + 1)) + 1) << (c + 1)) - 1);
          c++;
          ans++;
          r = nr;
        }
      } else {
        if (i < r) {
          c++;
          ans++;
          r--;
        } else if (i > r) {
          c++;
          ans++;
          r++;
        } else {
          c++;
          ans++;
        }
      }
      // cout << i << " " << j << "  " << r << " " << c << " " << ans << "!\n";
    }
    // assert((i >> j) == (r >> j));
    ans += abs(i - r);
    cout << ans << "\n";
  }
}