#include <bits/stdc++.h>
using namespace std;
long long n, m, d, ans;
signed main() {
  long long T;
  cin >> T;
  while (T--) {
    cin >> d >> m;
    if (d <= 3) {
      cout << (d * 2 - 1 + m) % m << "\n";
      continue;
    } else {
      long long x = 2, i;
      for (i = 4; i <= d; i <<= 1) {
        x = x * (i / 2 + 1) % m;
      }
      ans = (x * 2 % m - 1 + m) % m;
      i >>= 1;
      cout << (ans + (d - i) * x % m) % m << "\n";
    }
  }
  return 0;
}
