#include <bits/stdc++.h>
using namespace std;
inline void solve() {
  int d, m;
  scanf("%d%d", &d, &m);
  int ans = 1;
  for (int i = 0; (1 << i) <= d; ++i) {
    ans = 1ll * ans * ((1 << i) + 1) % m;
    d -= (1 << i);
  }
  if (d) ans = 1ll * ans * (d + 1) % m;
  printf("%d\n", (ans - 1 + m) % m);
}
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    solve();
  }
}
