#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void rd(T &x) {
  x = 0;
  char o, f = 1;
  while (o = getchar(), o < 48)
    if (o == 45) f = -f;
  do x = (x << 3) + (x << 1) + (o ^ 48);
  while (o = getchar(), o > 47);
  x *= f;
}
const int inf = ~0u >> 2;
const long long INF = ~0ull >> 2;
const int maxn = 100000 + 10;
long long d, mod;
void solve() {
  rd(d), rd(mod);
  long long now = 1;
  long long sum = 1;
  long long last = 1;
  while (now < d) {
    if (now % 2 == 0 && now * 2 - 1 >= d) {
      sum += last * (d - now);
      sum %= mod;
      now = d;
      break;
    }
    if (now & 1) {
      now = now + 1;
      last = sum + 1;
      sum *= 2ll;
      sum += 1ll;
      last %= mod;
      sum %= mod;
    } else {
      sum += last * (now - 1);
      sum %= mod;
      now <<= 1;
      now--;
    }
  }
  cout << (sum + mod) % mod << endl;
}
int main() {
  int t;
  rd(t);
  while (t--) solve();
  return 0;
}
