#include <bits/stdc++.h>
using namespace std;
const long long N = 1e3 + 10;
long long dp[N], d, m;
inline long long read() {
  char c = getchar();
  long long f = 1, x = 0;
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = (x << 1) + (x << 3) + (c ^ '0');
    c = getchar();
  }
  return x * f;
}
long long check(long long x) {
  long long cnt = 0;
  while (x > 0) x /= 2, cnt++;
  return cnt;
}
void solve() {
  memset(dp, 0, sizeof(dp));
  d = read(), m = read();
  long long num = check(d);
  dp[0] = 1;
  for (long long i = 1; i <= num - 1; i++) {
    long long x = (1 << (i - 1));
    for (long long j = 0; j <= i - 1; j++) dp[i] += x * dp[j] % m, dp[i] %= m;
  }
  long long x = d - ((1 << (num - 1)) - 1);
  for (long long j = 0; j <= num - 1; j++)
    dp[num] += x * dp[j] % m, dp[num] %= m;
  long long ans = 0;
  for (long long i = 1; i <= num; i++) ans += dp[i], ans %= m;
  cout << ans << '\n';
}
signed main() {
  long long t = read();
  while (t--) solve();
  return 0;
}
