#include <bits/stdc++.h>
using namespace std;
long long msb(long long d) {
  long long b = -1;
  while (d) {
    d /= 2;
    b++;
  }
  return b;
}
int main() {
  vector<long long> exp;
  exp.push_back(1);
  for (long long i = 1; i < 35; i++) {
    exp.push_back(2 * exp[i - 1]);
  }
  long long t;
  cin >> t;
  long long d, m, b, ans;
  while (t--) {
    cin >> d >> m;
    if (m == 1) {
      cout << 0 << '\n';
      continue;
    }
    b = msb(d);
    ans = (d - exp[b] + 2) % m;
    for (long long i = 0; i < b; i++) {
      ans = (ans * (exp[i] + 1)) % m;
    }
    cout << (ans == 0 ? m - 1 : ans - 1) << '\n';
  }
}
