#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  char c = getchar();
  long long t = 0, f = 1;
  while ((!isdigit(c)) && (c != EOF)) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while ((isdigit(c)) && (c != EOF)) {
    t = (t << 3) + (t << 1) + (c ^ 48);
    c = getchar();
  }
  return t * f;
}
long long t, d, mod, f[55][55];
inline long long ksm(long long a, long long b) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans = ans * a;
    b >>= 1;
    a = a * a;
  }
  return ans;
}
long long tot[55];
signed main() {
  t = read();
  while (t--) {
    memset(f, 0, sizeof(f));
    memset(tot, 0, sizeof(tot));
    d = read(), mod = read();
    long long tmp = log2(d);
    f[1][0] = 1;
    tot[0] = 1;
    for (long long i = 1; i <= tmp; i++) {
      f[1][i] = f[1][i - 1] * 2;
      tot[i] = f[1][i];
    }
    f[1][tmp] = d - f[1][tmp] + 1;
    tot[tmp] = f[1][tmp];
    long long ans = d % mod;
    for (long long i = 2; i <= tmp + 1; i++) {
      for (long long j = 0; j < tmp; j++) f[i][j + 1] = f[i - 1][j];
      for (long long j = 1; j <= tmp; j++) {
        f[i][j] = (f[i][j] + f[i][j - 1]) % mod;
      }
      for (long long j = 1; j <= tmp; j++) {
        f[i][j] = f[i][j] * tot[j] % mod;
        ans = (ans + f[i][j]) % mod;
      }
    }
    printf("%lld\n", ans);
  }
  return 0;
}
