#include <bits/stdc++.h>
using namespace std;
long long f[40];
long long pw[40];
int main() {
  int t;
  int n, p;
  int dig, tt;
  long long fk, ans;
  scanf("%d", &t);
  while (t--) {
    scanf("%d%d", &n, &p);
    ans = 0;
    pw[0] = 1 % p;
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= 30; ++i) pw[i] = pw[i - 1] * 2 % p;
    for (dig = 1, tt = 1; tt <= n; ++dig, tt <<= 1)
      ;
    --dig;
    fk = 1 << (dig - 1);
    f[0] = 1 % p;
    for (int i = 1; i < dig; ++i) {
      for (int j = 0; j < i; ++j) {
        f[i] += pw[i - 1] * f[j] % p;
        f[i] %= p;
      }
      ans += f[i];
    }
    for (int i = 0; i < dig; ++i) {
      f[dig] += (n - fk + 1) * f[i] % p;
      f[dig] %= p;
    }
    printf("%lld\n", (ans + f[dig]) % p);
  }
  return 0;
}
