#include <bits/stdc++.h>
using namespace std;
void solve() {
  long long d, m;
  long long running = 1;
  long long accum = 0;
  long long x = 0;
  long long diff;
  scanf("%lld %lld\n", &d, &m);
  x = 1;
  while ((x << 1) <= d) {
    running += (accum % m) * ((x - 1) % m);
    running %= m;
    accum = (running + 1) % m;
    running = ((2 * running) + 1) % m;
    x <<= 1;
  }
  running %= m;
  accum %= m;
  diff = (d - x) % m;
  running += (accum * diff) % m;
  running %= m;
  printf("%lld\n", running);
}
int main() {
  int T;
  scanf("%d\n", &T);
  while (T--) {
    solve();
  }
  return 0;
}
