#include <bits/stdc++.h>
using namespace std;
bool build(vector<int>& v) {
  vector<int> b;
  b.push_back(v[0]);
  for (int i = 0; i < v.size(); i++) {
    if (i == 0) continue;
    b.push_back(b.back() ^ v[i]);
    if (b.back() <= b[b.size() - 2]) {
      return false;
    }
  }
  return true;
}
int vals[] = {1, 3, 5};
int main() {
  int t;
  cin >> t;
  while (t--) {
    long long int d, m;
    cin >> d >> m;
    if (d <= 3) {
      cout << vals[d - 1] % m << endl;
      continue;
    }
    long long int len = 4;
    long long int i = 2;
    long long int last = 5;
    while (true) {
      if (len + 2 * i <= d) {
        i *= 2;
        last += ((last + 1) * (i)) % m;
        len += i;
      } else {
        long long int dist = (d - len + 1);
        cout << (last + (last + 1) * (dist)) % m << endl;
        break;
      }
    }
  }
  return 0;
}
