#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 2e5 + 5;
const long long MOD = 1e9 + 7;
const long long INF = 1e18;
mt19937 rnd(time(0));
signed main() {
  long long q;
  cin >> q;
  while (q--) {
    long long d, mod;
    cin >> d >> mod;
    long long c = 1;
    long long lg = 0;
    while ((1ll << lg) <= d) {
      c = (c * (min(d, (1ll << (lg + 1)) - 1) - (1ll << lg) + 2ll)) % mod;
      lg++;
    }
    c--;
    if (c < 0) {
      c += mod;
    }
    cout << c << "\n";
  }
  return 0;
}
