#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void MAX(T &x, T y) {
  if (y > x) x = y;
}
template <class T>
inline void MIN(T &x, T y) {
  if (y < x) x = y;
}
template <class T>
inline void rd(T &x) {
  x = 0;
  char o, f = 1;
  while (o = getchar(), o < 48)
    if (o == 45) f = -f;
  do x = (x << 3) + (x << 1) + (o ^ 48);
  while (o = getchar(), o > 47);
  x *= f;
}
const int M = 105;
int cas, d, m, A[M];
int main() {
  rd(cas);
  while (cas--) {
    rd(d), rd(m);
    int n = 0;
    for (int i = 1, num = 1; num <= d; i++, num = num * 2) {
      n++;
      A[i] = 1 << i - 1;
      if (num * 2 > d) A[i] = d - num + 1;
    }
    int ans = 1;
    for (int i = 1; i <= n; i++) ans = 1ll * ans * (A[i] + 1) % m;
    ans--;
    if (ans < 0) ans += m;
    printf("%d\n", ans);
  }
  return (0 - 0);
}
