#include <bits/stdc++.h>
using namespace std;
int pow(int, int, int);
int dp[50][50];
int C[50];
int num[50], ct;
void init();
void work();
int ca = 1;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int T;
  cin >> T;
  while (T--) work();
  return 0;
}
void work() {
  int d, m;
  cin >> d >> m;
  ct = -1;
  int D = d;
  while (d) {
    num[++ct] = d & 1;
    d >>= 1;
  }
  for (int i = 0; i < ct; i++) {
    C[i] = (1 << i) % m;
  }
  C[ct] = D - (1 << (ct)) + 1;
  C[ct] %= m;
  int mod = m;
  memset(dp, 0, sizeof(dp));
  for (int i = 0; i <= ct; i++) dp[0][i] = C[i];
  for (int i = 1; i <= ct; i++) {
    for (int j = i; j <= ct; j++) {
      for (int k = 0; k < j; k++) {
        dp[i][j] = (dp[i][j] + dp[i - 1][k]) % mod;
      }
      dp[i][j] = 1LL * dp[i][j] * C[j] % mod;
    }
  }
  int ans = 0;
  for (int i = 0; i <= ct; i++) {
    for (int j = i; j <= ct; j++) ans = (ans + dp[i][j]) % mod;
  }
  ans = (ans + mod) % mod;
  cout << ans << '\n';
}
