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