#include <bits/stdc++.h>
using namespace std;
template <class T, class T2>
inline bool chkmax(T &x, const T2 &y) {
  return x < y ? x = y, 1 : 0;
}
template <class T, class T2>
inline bool chkmin(T &x, const T2 &y) {
  return x > y ? x = y, 1 : 0;
}
long long mod = 1e9 + 7;
template <class T>
inline void fix(T &x) {
  if (x >= mod | x <= -mod) {
    x %= mod;
  }
  if (x < 0) {
    x += mod;
  }
}
const long long MAX_N = 70l;
long long prec[MAX_N];
long long ret(long long n) {
  for (long long i = 0; i < MAX_N; i++) {
    if (i == 0) {
      prec[i] = 1;
      continue;
    }
    prec[i] = prec[i - 1] * ((1LL << (i - 1)) % mod + 1LL);
    prec[i] %= mod;
  }
  long long p = 1;
  long long currd = 1;
  long long ans = 1;
  while (true) {
    long long now = (1ll << p);
    if (currd + now <= n) {
      ans += ((now % mod) * prec[p]) % mod;
      ans %= mod;
      currd += now;
    } else {
      break;
    }
    p++;
  }
  ans += ((n - currd) * prec[p]) % mod;
  ans %= mod;
  return ans;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long t;
  cin >> t;
  while (t--) {
    long long n;
    cin >> n >> mod;
    cout << ret(n) << "\n";
  }
  return 0;
  return 0;
}
