#include <bits/stdc++.h>
using namespace std;
long long max(long long x, long long y) { return x > y ? x : y; }
long long min(long long x, long long y) { return x < y ? x : y; }
void solve() {
  long long d, m;
  cin >> d >> m;
  vector<long long> v;
  long long mod = m;
  for (long long i = 0;; i++) {
    if ((1ll << i) <= d) {
      v.push_back(min(d, (1ll << (i + 1)) - 1) - (1ll << i) + 1);
    } else
      break;
  }
  for (int i = 0; i < v.size(); ++i) {
    v[i] %= m;
  }
  long long n = v.size();
  long long dp[n][n];
  long long dd[n];
  memset(dp, 0, sizeof(dp));
  for (int i = 0; i < n; ++i) {
    dp[0][i] = v[i];
    dd[i] = v[i];
    if (i) dd[i] = ((dd[i] % mod) + (dd[i - 1] % mod)) % mod;
  }
  for (long long i = 1; i < n; i++) {
    long long ddd[n];
    ddd[0] = 0;
    for (int j = 1; j < n; ++j) {
      dp[i][j] = ((dd[j - 1] % mod) * (v[j] % mod)) % mod;
      ddd[j] = dp[i][j];
      ddd[j] = ((ddd[j] % mod) + (ddd[j - 1]) % mod) % mod;
    }
    for (int j = 0; j < n; ++j) {
      dd[j] = ddd[j];
    }
  }
  long long ans = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      ans = ((ans % m) + (dp[i][j] % m)) % m;
    }
  }
  cout << ans << "\n";
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long t;
  cin >> t;
  while (t--) {
    solve();
  }
}
