#include <bits/stdc++.h>
using namespace std;
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  os << "[";
  for (int i = 0; i < v.size(); ++i) {
    os << v[i];
    if (i != v.size() - 1) os << ", ";
  }
  os << "]\n";
  return os;
}
template <typename T>
ostream& operator<<(ostream& os, const deque<T>& v) {
  os << "[";
  for (int i = 0; i < v.size(); ++i) {
    os << v[i];
    if (i != v.size() - 1) os << ", ";
  }
  os << "]\n";
  return os;
}
template <typename T>
ostream& operator<<(ostream& os, const set<T>& v) {
  os << "[";
  for (auto it : v) {
    os << it;
    if (it != *v.rbegin()) os << ", ";
  }
  os << "]\n";
  return os;
}
template <typename T, typename S>
ostream& operator<<(ostream& os, const map<T, S>& v) {
  for (auto it : v) os << it.first << " : " << it.second << "\n";
  return os;
}
template <typename T, typename S>
ostream& operator<<(ostream& os, const pair<T, S>& v) {
  os << "(";
  os << v.first << ", " << v.second << ")";
  return os;
}
void go() { cin.tie(nullptr)->sync_with_stdio(false); }
long long d, m;
long long dp[34][34];
long long msb;
long long solve(long long index, long long pos) {
  if (pos > msb) return 0;
  long long& ans = dp[index][pos];
  if (ans != -1) return ans;
  if (pos < msb) {
    ans = (1 << pos);
    for (long long i = pos + 1; i <= 30; i++) {
      if (i <= msb) {
        long long p = solve(index + 1, i);
        ans = (ans + ((p) * (1LL << pos)) % m) % m;
      }
    }
  } else {
    ans = (d - (1LL << pos) + 1) % m;
  }
  return ans;
}
void solve_case() {
  memset(dp, -1, sizeof(dp));
  cin >> d >> m;
  for (long long i = 30; i >= 0; --i) {
    if (d >> i & 1) {
      msb = i;
      break;
    }
  }
  long long ans = 0;
  for (long long i = 0; i < 30; i++) {
    ans = (ans + solve(0, i) % m) % m;
  }
  cout << ans << '\n';
}
signed main() {
  go();
  long long t;
  cin >> t;
  while (t--) {
    solve_case();
  }
}
