#include <bits/stdc++.h>
using namespace std;
const long long int MOD = 1000000007;
const long long int INF = (long long int)1e15;
long long int P[33];
long long int dp[33][33];
long long int solve(long long int d, long long int m) {
  memset(P, 0, sizeof(P));
  P[0] = 1;
  long long int p = 1;
  for (long long int(i) = (0); (i) < (31); ++(i)) {
    p *= 2LL;
    if (p * 2LL <= d)
      P[i + 1] = p;
    else
      P[i + 1] = std::max(0LL, d - p + 1);
  }
  long long int ret = 0;
  for (long long int n = 1; n <= 31; ++n) {
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    for (long long int(i) = (0); (i) < (31); ++(i)) {
      for (long long int(j) = (0); (j) < (n + 1); ++(j)) {
        dp[i + 1][j] += dp[i][j];
        if (j > 0) dp[i + 1][j] += (dp[i][j - 1] * P[i]);
        dp[i + 1][j] %= m;
      }
    }
    ret += dp[31][n];
    ret %= m;
  }
  return ret % m;
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  long long int Q;
  cin >> Q;
  for (long long int(_) = (0); (_) < (Q); ++(_)) {
    long long int D, M;
    cin >> D >> M;
    cout << solve(D, M) << endl;
  }
  return 0;
}
