#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  long long s = 0, w = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
  return s * w;
}
void put1() { puts("Yes"); }
void put2() { puts("No"); }
void put3() { puts("-1"); }
long long qp(long long a, long long b, long long p) {
  long long ans = 1;
  while (b) {
    if (b & 1) {
      ans = (ans * a) % p;
      --b;
    }
    a = (a * a) % p;
    b >>= 1;
  }
  return ans % p;
}
const unsigned long long base = 2333;
const unsigned long long pp = 19260811;
const unsigned long long ppp = 999998639;
const int manx = 5e5 + 5;
const int mo = 998244353;
long long dp[manx];
int main() {
  long long p = read();
  while (p--) {
    long long d = read(), m = read();
    long long ans = 1;
    for (int i = 0; i < 30; i++) {
      long long x = (1 << i);
      if (d < x) break;
      ans = ans * (min((x << 1) - 1ll, d) - x + 1 + 1) % m;
    }
    ans = (ans - 1 + m) % m;
    printf("%lld\n", ans);
  }
  return 0;
}
