#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e5 + 2;
const int M = 1e9 + 7;
long long d, m;
void solve() {
  cin >> d >> m;
  long long ans = 1;
  for (long long i = 1;; i <<= 1) {
    if (i * 2 > d) {
      ans *= (d - i + 2);
      break;
    }
    if (i == d) {
      ans *= 2;
      break;
    }
    ans *= (i + 1);
    ans %= m;
  }
  ans = (ans - 1 + m) % m;
  cout << ans << "\n";
}
int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  int T;
  cin >> T;
  while (T--) solve();
}
