#include <bits/stdc++.h>
using namespace std;
void Solve() {
  long long d, mod;
  cin >> d >> mod;
  vector<long long> available;
  long long cnt = 1, next = 1;
  long long pwr = 2;
  while (cnt <= d) {
    available.push_back(next);
    cnt += pwr;
    next = pwr;
    pwr *= 2;
  }
  long long extra = cnt - d;
  if (extra != next) {
    available.push_back(next - extra);
  }
  long long n = available.size();
  long long ncr[n + 1][n + 1];
  for (long long i = 0; i <= n; i++) {
    for (long long j = 0; j <= n; j++) {
      ncr[i][j] = 0;
    }
  }
  for (long long i = 1; i <= n; i++) {
    ncr[i][1] = available[i - 1] % mod;
  }
  for (long long i = 2; i <= n; i++) {
    for (long long j = 2; j <= i; j++) {
      for (long long last = i - 1; last >= j - 1; last--) {
        long long x = ncr[last][j - 1] * available[i - 1];
        x %= mod;
        ncr[i][j] += x;
        ncr[i][j] %= mod;
      }
    }
  }
  long long ans = 0;
  for (long long i = 1; i <= n; i++) {
    for (long long j = 1; j <= i; j++) {
      ans += ncr[i][j];
      ans %= mod;
    }
  }
  cout << ans << "\n";
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  long long t;
  cin >> t;
  while (t--) {
    Solve();
  }
  return 0;
}
