#include <bits/stdc++.h>
using namespace std;
int main(void) {
  int q;
  scanf("%d", &q);
  while (q--) {
    long long ans = 0, n, p;
    scanf("%lld %lld", &n, &p);
    for (long long x = 1, s = 1; x <= n; x *= 2) {
      long long nx = min(x * 2, n + 1);
      long long t = s * (nx - x) % p;
      ans = (ans + t) % p;
      s = (s + t) % p;
    }
    printf("%lld\n", ans);
  }
}
