#include <bits/stdc++.h>
using namespace std;
long long productOfSubsetSums(vector<long long> arr, long long n, long long m) {
  long long ans = 1;
  for (long long i = 0; i < n; ++i) {
    ans *= (arr[i] + 1);
    ans %= m;
  }
  long long f = (ans - 1 + m);
  f %= m;
  return f;
}
signed main() {
  long long t;
  cin >> t;
  vector<long long> vec;
  while (t--) {
    vec.clear();
    long long n, m;
    cin >> n >> m;
    long long sum = 0;
    for (long long i = 0; i <= 31; ++i) {
      long long f = pow(2, i);
      if (sum + f > n)
        break;
      else {
        vec.push_back(f);
        sum += f;
      }
    }
    if (n - sum) vec.push_back(n - sum);
    long long q = productOfSubsetSums(vec, vec.size(), m);
    cout << q << endl;
  }
  return 0;
}
