#include <bits/stdc++.h>
using namespace std;
void setIO(string name) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  if (name == "input") {
    freopen("input.txt", "r", stdin);
  } else if (name == "stdio") {
  } else {
    freopen((name + ".in").c_str(), "r", stdin);
    freopen((name + ".out").c_str(), "w", stdout);
  }
}
const int INF = INT_MAX;
const int NINF = INT_MIN;
const int MAXLOG = 21;
const int MAXSEG = (1 << 18);
const int MUL = 1000001;
const int MOD = 1000000007;
long long dp[33][33];
int main() {
  setIO("stdio");
  int t;
  cin >> t;
  dp[0][0] = 1;
  for (int rv = (0); rv < (t); ++rv) {
    long long d, m;
    cin >> d >> m;
    int sz = d ? 32 - __builtin_clz(d) : NINF;
    for (int i = (1); i < (sz + 1); ++i) {
      long long mul = 1;
      long long pre = 0;
      for (int j = (1); j < (sz + 1); ++j) {
        if (j == sz) {
          mul = d - (1 << (sz - 1)) + 1;
        }
        pre = (pre + dp[i - 1][j - 1]) % m;
        dp[i][j] = (pre * mul) % m;
        mul *= 2;
      }
    }
    long long ans = 0;
    for (int i = (1); i < (sz + 1); ++i) {
      for (int j = (1); j < (sz + 1); ++j) {
        ans = (ans + dp[i][j]) % m;
      }
    }
    cout << ans << '\n';
  }
}
