#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  long long freq[31];
  long long ans[31];
  while (t--) {
    long long d, m;
    cin >> d >> m;
    long long prod = 1;
    memset(freq, 0, sizeof(freq));
    int sz = 0;
    for (int i = 0; i <= 30; i++) {
      if (2 * prod <= d)
        freq[i] = prod;
      else {
        freq[i] = d - prod + 1;
        sz = i;
        break;
      }
      prod *= 2;
    }
    memset(ans, 0, sizeof(ans));
    for (int i = sz; i >= 0; i--) {
      long long val = 1;
      for (int j = i + 1; j <= sz; j++) {
        val += ans[j];
        val %= m;
      }
      val *= freq[i];
      val %= m;
      ans[i] = val;
    }
    long long tot = 0;
    for (int i = 0; i <= sz; i++) {
      tot += ans[i];
      tot %= m;
    }
    cout << tot << "\n";
  }
}
