#include <bits/stdc++.h>
using namespace std;
int main() {
  int t;
  cin >> t;
  while (t--) {
    long long d, m;
    cin >> d >> m;
    long long ans = d;
    long long n = log2(d) + 1;
    for (long long i = 2; i <= n; i++) {
      long long dp[i][n + 1];
      memset(dp, 0, sizeof(dp));
      for (long long k = 0; k <= n; k++) {
        if (((long long)1 << (k + 1)) - 1 <= d)
          dp[0][k] = ((long long)1 << (k));
        else {
          long long val = d - ((long long)1 << (k));
          dp[0][k] = val + 1;
          break;
        }
      }
      for (int k = 1; k <= n; k++) {
        dp[0][k] = (dp[0][k] + dp[0][k - 1]) % m;
      }
      for (long long j = 1; j < i; j++) {
        for (long long k = 1; k <= n; k++) {
          if (((long long)1 << (k + 1)) - 1 <= d)
            dp[j][k] = (dp[j - 1][k - 1] * (((long long)1 << (k)))) % m;
          else {
            long long val = d - ((long long)1 << (k));
            dp[j][k] = (dp[j - 1][k - 1] * (val + 1)) % m;
            break;
          }
        }
        for (int k = 1; k <= n; k++) {
          dp[j][k] = (dp[j][k] + dp[j][k - 1]) % m;
        }
      }
      ans = (ans + dp[i - 1][n]) % m;
    }
    cout << ans % m << "\n";
  }
  return 0;
}
