#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
int main() {
  ll d, m;
  ll t;
  cin >> t;
  for (int _ = 0; _ < t; ++_) {
    cin >> d >> m;
    ll temp = 1;
    vector<ll> v;
    while (2 * temp <= d) {
      v.push_back(temp + 1);
      temp *= 2;
    }
    v.push_back(d - temp + 2);
    ll act = 1 % m;
    for (int i = 0; i < (int)(v).size(); ++i) {
      act *= v[i];
      act = act % m;
    }
    act += m - 1;
    act = act % m;
    cout << act << endl;
  }
}
