#include <bits/stdc++.h>
using namespace std;
void test(int t) {
  int cnt = 0;
  for (int i = 1; i < (1 << t); ++i) {
    int x = i;
    vector<int> a_;
    for (int j = 0; j < t; ++j) {
      a_.push_back(x & 1);
      x >>= 1;
    }
    vector<int> a;
    vector<int> b;
    bool pizda = false;
    for (int j = 0; j < t; ++j) {
      if (a_[j]) {
        a.push_back(j + 1);
        if (b.size() == 0) {
          b.push_back(j + 1);
        } else {
          int bNext = (b.back() ^ (j + 1));
          if (bNext > b.back()) {
            b.push_back(bNext);
          } else {
            pizda = true;
            break;
          }
        }
      }
    }
    if (!pizda) {
      cnt++;
    }
  }
  cout << t << " " << cnt << endl;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    long long d, m;
    cin >> d >> m;
    int currX = 1;
    long long currY = 1;
    long long delta = 2;
    while (currX * 2 <= d) {
      long long delta1 = delta * (currX - 1) % m;
      long long y = (currY + delta1) % m;
      currX *= 2;
      currY = (2 * y + 1) % m;
      delta = (y + 1) % m;
    }
    long long ans = (currY + ((d - currX) * delta) % m) % m;
    cout << ans << endl;
  }
  return 0;
}
