#include <bits/stdc++.h>
long long T;
long long D, M;
int log2(long long n) {
  int conta = 0;
  while (n != 1) {
    conta++;
    n /= 2;
  }
  return conta;
}
int main() {
  scanf("%d", &T);
  for (int t = 0; t < T; t++) {
    long long tot = 0;
    scanf("%lld %lld", &D, &M);
    int maxi = log2(D);
    int pdd = 1 << maxi;
    int initposs = D - pdd + 1;
    for (int i = maxi; i >= 0; i--) {
      if (i == maxi) {
        tot = (tot + initposs) % M;
        continue;
      }
      long long poss = (1 << i) % M;
      poss = (poss + ((poss * tot) % M)) % M;
      tot = (tot + poss) % M;
    }
    printf("%lld\n", tot);
  }
}
