#include <bits/stdc++.h>
using namespace std;
template <typename _T, typename _T2>
string to_string(pair<_T, _T2> x) {
  return "<" + to_string(x.first) + ", " + to_string(x.second) + ">";
}
template <typename _T>
string to_string(vector<_T> vec) {
  string s = "[ ";
  for (auto el : vec) s += to_string(el) + ", ";
  s[s.size() - 1] = ']';
  s[s.size() - 2] = ' ';
  return s;
}
template <typename _T>
string to_string(set<_T> vec) {
  string s = "{ ";
  for (auto el : vec) s += to_string(el) + ", ";
  s[s.size() - 1] = '}';
  s[s.size() - 2] = ' ';
  return s;
}
template <typename _T, typename _T2>
string to_string(map<_T, _T2> vec) {
  string s = "{ ";
  for (auto el : vec)
    s += "mp[" + to_string(el.first) + "]= " + to_string(el.second) + ", ";
  s[s.size() - 1] = '}';
  s[s.size() - 2] = ' ';
  return s;
}
template <typename _T>
inline void _DBG(const char *s, _T x) {
  cerr << s << " = " << to_string(x) << "\n";
}
template <typename _T, typename... args>
void _DBG(const char *s, _T x, args... a) {
  while (*s != ',') cerr << *s++;
  cerr << " = " << to_string(x) << "\n";
  _DBG(s + 1, a...);
}
mt19937 rng___(chrono::steady_clock::now().time_since_epoch().count());
const long long MOD = 998244353;
const long long LLINF = 1e18 + 7;
long long d, m;
long long powe(long long n, long long k) {
  if (k == 0) return 1;
  long long pom = powe(n, k / 2);
  pom = (pom * pom) % m;
  if (k & 1) pom = (pom * n) % m;
  return pom;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  ;
  int t;
  cin >> t;
  while (t--) {
    cin >> d >> m;
    long long dp[32][32];
    for (int i = 0; i < 32; i++)
      for (int j = 0; j < 32; j++) dp[i][j] = 0;
    dp[0][0] = 1;
    long long ans = 0;
    for (int i = 1; i < 32; i++) {
      for (int j = 1; j < 32; j++) {
        int b = j - 1;
        if ((1 << b) > d) break;
        long long summ = 0;
        for (int k = 0; k < j; k++) {
          summ += dp[i - 1][k];
        }
        summ = summ % m;
        dp[i][j] = (summ * 1LL * min(d - (1 << b) + 1, 1LL << b)) % m;
        ans = (ans + dp[i][j]) % m;
      }
    }
    cout << ans << '\n';
  }
}
