#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int N = 5e5 + 2;
void solve() {
  long long int d, m;
  cin >> d >> m;
  vector<long long int> bit_cnt;
  for (long long int p = 1;; p *= 2) {
    if (d >= p) {
      bit_cnt.push_back(p);
      d -= p;
    } else {
      bit_cnt.push_back(d);
      break;
    }
  }
  if (bit_cnt.back() == 0) bit_cnt.pop_back();
  long long int ans = 1;
  for (long long int i = 0; i < (int)bit_cnt.size(); i++) {
    ans *= (bit_cnt[i] + 1);
    ans %= m;
  }
  --ans;
  cout << (ans + m) % m << "\n";
  return;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int t = 1;
  cin >> t;
  while (t--) solve();
  return 0;
}
