#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template <typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
double startTime;
double getCurrentTime() {
  return ((double)clock() - startTime) / CLOCKS_PER_SEC;
}
void solve() {
  ll d, m;
  scanf("%lld%lld", &d, &m);
  ll ans = 1;
  for (int k = 0; k < 30; k++) {
    ll l = 1LL << k, r = 1LL << (k + 1);
    r = min(r, d + 1);
    r -= l;
    r = max(r, 0LL);
    ans = (ans * (r + 1)) % m;
  }
  ans--;
  ans %= m;
  if (ans < 0) ans += m;
  printf("%lld\n", ans);
}
int main() {
  startTime = (double)clock();
  int t;
  scanf("%d", &t);
  while (t--) solve();
  return 0;
}
