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

const int N = 1e5 + 5;

i64 P, m, ans;

i64 Div(i64 x, i64 y) { return floor(1.0 * x / y) + 1; }

void dfs(i64 x, int k, i64 s) {
    if (k == -1) {
        ans += (s == 1);
        return;
    }
    if (x >> k & 1) {
        // 0
        i64 num = s;
        if ((P - 1) >> k & 1) {
            num = ((num + (1ll << k) % P) % P + P) % P;
        }
        if (k > 0) {
            i64 y = ((1ll - num) % P + P) % P;
            i64 tot = (1ll << (k - 1)) - 1;
            ans += Div(tot - y, P);
            cout << x << " " << k << " " << s << " " << tot << " " << y << " " << Div(tot - y, P)
                 << "\n";
        } else {
            if (num == 1) {
                ans++;
            }
        }
        // 1
        num = s;
        if (((P - 1) >> k & 1) == 0) {
            num = ((num + (1ll << k) % P) % P + P) % P;
        }
        dfs(x, k - 1, num);
    } else {
        if ((P - 1) >> k & 1) {
            dfs(x, k - 1, ((s + (1ll << k) % P) % P + P) % P);
        } else {
            dfs(x, k - 1, s);
        }
    }
}

void solve() {
    cin >> P >> m;
    ans = 0;
    dfs(m, 62, 0);
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}