#include <bits/stdc++.h>
using namespace std;
const int N = (2e6 + 5);
const int mod = 1e9 + 7;
long long int n, m, k, sz, a[N], l, r, ans;
long long int pow_mod_m(long long int a, long long int n) {
  if (!n) return 1;
  long long int pt = pow_mod_m(a, n / 2);
  pt *= pt;
  pt %= mod;
  if (n & 1) pt *= a, pt %= mod;
  return pt;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  int ts = 1;
  cin >> ts;
  while (ts--) {
    cin >> n >> m;
    ans = 1;
    for (long long int i = 0; i < 30; ++i) {
      if (n < (1 << i)) break;
      ans =
          ans * (min((long long int)(1 << (i + 1)) - 1, n) - (1 << i) + 2) % m;
    }
    ans--;
    if (ans < 0) ans += m;
    cout << ans << "\n";
  }
}
