#include <bits/stdc++.h>
using namespace std;
long long dp[105], b[105];
int main() {
  std::ios::sync_with_stdio(false);
  long long d, m;
  int t;
  cin >> t;
  while (t--) {
    cin >> d >> m;
    memset(b, 0, sizeof(b));
    memset(dp, 0, sizeof(dp));
    long long x = d;
    long long s = 1, k = 1;
    while (x) {
      b[k++] = min(s, d - s + 1);
      x >>= 1;
      s <<= 1;
    }
    for (int i = 1; i < k; i++)
      dp[i] = (dp[i - 1] + b[i] % m + dp[i - 1] * b[i] % m) % m;
    cout << dp[k - 1] << endl;
  }
  return 0;
}
