#include <bits/stdc++.h>
using namespace std;
long long tt;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> tt;
  while (tt--) {
    long long d, m;
    vector<long long> dp;
    cin >> d >> m;
    dp.assign(log2(d) + 2, 0);
    dp[0] = 1;
    for (long long i = 1; i <= 32; ++i) {
      if ((1LL << (i - 1)) > d) break;
      for (int j = 0; j < i; ++j) {
        dp[i] += dp[j];
        dp[i] %= m;
      }
      dp[i] *= min(d, (1LL << i) - 1) - ((1LL << (i - 1)) - 1);
      dp[i] %= m;
    }
    long long res = 0;
    for (int i = 1; i < dp.size(); ++i) res += dp[i];
    cout << (res % m) << "\n";
  }
  return 0;
}
