#include <bits/stdc++.h>
using namespace std;
int main() {
  int t;
  cin >> t;
  while (t--) {
    long long n, m;
    cin >> n >> m;
    vector<int> s;
    for (long long i = 0; (1 << i) <= n; i++) {
      if (n >= (1 << (i + 1)))
        s.push_back((1 << i));
      else
        s.push_back(n - (1 << i) + 1);
    }
    long long sum = 1;
    for (int i = 0; i < s.size(); i++) {
      sum *= (s[i] + 1ll);
      sum %= m;
      if (sum == 0) sum = m;
    }
    sum--;
    cout << sum << endl;
  }
}
