#include <bits/stdc++.h>
using namespace std;
const long long int mod = 1e9 + 7;
int main() {
  int t, i, cnt;
  long long int d, m, pows[35], ans;
  pows[0] = 1;
  for (i = 1; i <= 35; i++) pows[i] = (pows[i - 1] * 2);
  cin >> t;
  while (t--) {
    cin >> d >> m;
    long long int j = 1;
    cnt = 0;
    while (j <= d + 1) {
      j <<= 1;
      cnt++;
    }
    j >>= 2;
    cnt -= 1;
    ans = 1;
    for (i = 2; i <= cnt; i++) {
      ans = ((ans * (pows[i - 1] + 1) % m) % m + pows[i - 1]) % m;
    }
    ans = ((ans * (d - 2 * j + 2) % m) % m + d - 2 * j + 1) % m;
    cout << ans << endl;
  }
  return 0;
}
