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