#include <bits/stdc++.h>
int T, lim, mod;
int main() {
  scanf("%d", &T);
  for (int cs = 1; cs <= T; cs++) {
    scanf("%d%d", &lim, &mod);
    int ans = 1;
    for (int i = 1; (1 << (i - 1)) <= lim; i++) {
      ans = (long long)ans *
            (std::min((1 << i) - 1, lim) - (1 << (i - 1)) + 2) % mod;
    }
    printf("%d\n", (ans - 1 + mod) % mod);
  }
  return 0;
}
