#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long T;
  cin >> T;
  while (T--) {
    long long D, M;
    cin >> D >> M;
    long long req[31] = {0};
    for (long long i = 0; i < 31; ++i) {
      if ((1 << i) <= D)
        req[i] = (1 << i);
      else {
        req[i - 1] = D % req[i - 1] + 1;
        break;
      }
    }
    long long dp[31][31] = {0};
    long long res = 0;
    for (long long i = 0; i < 31; ++i) dp[0][i] = 1;
    dp[1][0] = req[0];
    for (long long l = 1; l < 31; ++l) {
      for (long long i = 1; i < 31; ++i) {
        if (l <= (i + 1))
          dp[l][i] = ((dp[l][i - 1] % M) +
                      ((dp[l - 1][i - 1] % M) * (req[i] % M)) % M) %
                     M;
      }
      res = ((res % M) + (dp[l][31 - 1] % M)) % M;
    }
    cout << res << endl;
  }
}
