#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
using namespace std;
const long double eps = 1e-9;
const long double PI = acos(-1);
const long long inf = 1e18 + 1329;
const long double E = 2.71828182845904523536028747135266249775724709369995;
vector<long long> mods = {1000065757, 1000570057, 1004571329,
                          1000580179, 1000057769, 1000001329,
                          1000006957, 1000056157, 1001001329};
vector<long long> hashpows = {29, 31, 37, 43, 47, 53, 59, 157, 179, 257};
mt19937 rnd((unsigned int)chrono::high_resolution_clock::now()
                .time_since_epoch()
                .count() +
            (unsigned int)1329);
long long hashmod = mods[rnd() % mods.size()];
long long hashpow = hashpows[rnd() % hashpows.size()];
template <class T>
istream& operator>>(istream& stream, vector<T>& v) {
  for (int i = 0; i < v.size(); ++i) {
    cin >> v[i];
  }
  return stream;
}
template <class T>
ostream& operator<<(ostream& stream, vector<T>& v) {
  for (int i = 0; i < v.size(); ++i) {
    cout << v[i] << " ";
  }
  cout << '\n';
  return stream;
}
signed main() {
  ios_base::sync_with_stdio(0);
  cout.tie(0);
  cin.tie(0);
  srand((unsigned long long)time(NULL));
  long long t;
  cin >> t;
  while (t--) {
    long long d, m;
    cin >> d >> m;
    vector<long long> cnt(31, 0);
    for (long long i = 0; i < 31; ++i) {
      long long x = min((1ll << i), d - ((1ll << i) - 1));
      cnt[i] = max((long long)0, x) % m;
    }
    long long ans = 1;
    for (long long i = 0; i < 31; ++i) {
      ans = (ans * (cnt[i] + 1)) % m;
    }
    cout << (ans - 1 + m) % m << '\n';
  }
}
