//#pragma GCC optimize("Ofast")
#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <string>
#include <map>
#include <queue>
#include <unordered_map>
#include <numeric>
#include <cstring>
#include <assert.h>
#include <set>
#include <ctime>
#include <functional>
#define lowbit(x) (x & -x)
using ll = long long;
const int N = 3e5 + 5, INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3fll;
const ll mod = 998244353, G = 3, Gi = 332748118;
const long double EPS = 1e-9;
namespace fast_IO {
    // char buf[N], *s, *t;
    // char getchar() {
    //     return (s == t) && (t = (s = buf) + fread(buf, 1, N, stdin)), s == t ? -1
    //     : *s++;
    // }
    ll read() {
        ll num = 0;
        char c;
        bool tag = false;
        while ((c = getchar()) != '-' && c != '+' && (c < '0' || c > '9') && ~c);
        if (!~c)return EOF;
        if (c == '-')tag = true;
        else if (c == '+')tag = false;
        else num = c ^ 48;
        while ((c = getchar()) >= '0' && c <= '9')
            num = (num << 1) + (num << 3) + (c ^ 48);
        if (tag)return -num;
        return num;
    }
    void speedup() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(0); std::cout.tie(0);
    }
}
void solve() {
    ll p, m; scanf("%lld%lld", &p, &m);
    ll ans = 0;
    for (ll k = 1; k <= m + p - 1; k += p) {
        if ((k ^ (p - 1)) <= m) {
            ++ans;
        }
    }
    printf("%lld\n", ans);
}

int main() {
    // freopen("data.in", "r", stdin);
    // int ti = clock();
    int T; scanf("%d", &T);
    while (T--) {
        solve();
    }
    // std::cout << clock() - ti;
    return 0;
}