#include <bits/stdc++.h>
using namespace std;
long long modpow(long long base, long long exponent, long long modulus) {
  if (base == 0 && exponent == 0) return 0;
  long long result = 1;
  while (exponent > 0) {
    if (exponent % 2 == 1) result = (result * base) % modulus;
    exponent = exponent >> 1;
    base = (base * base) % modulus;
  }
  return result;
}
int A[200110], B[200110], ans[200110];
int t;
long long D, M;
long long dp[40];
inline void ReadInput(void) {
  scanf("%lld", &D);
  scanf("%lld", &M);
}
inline void solve(void) {
  long long c = 1, m = 1;
  while (1) {
    c *= 2;
    m++;
    if (c > D) break;
  }
  c = 1;
  long long ans = 0;
  dp[0] = 1 % M;
  for (int i = 1; i < m; i++) {
    dp[i] = 0;
    long long add;
    for (int j = 0; j < i; j++) {
      add = (dp[j] * max(0LL, min(c, D - c + 1))) % M;
      dp[i] = (dp[i] + add) % M;
    }
    c *= 2;
    ans = (ans + dp[i]) % M;
  }
  cout << ans << endl;
}
inline void Refresh(void) {}
int main() {
  scanf("%d", &t);
  while (t--) {
    ReadInput();
    solve();
  }
  return 0;
}
