#include <bits/stdc++.h>
using namespace std;
signed main(void) {
  long long t = 1;
  cin >> t;
  while (t--) {
    long long d, m;
    cin >> d >> m;
    long long p = d - (d % 2);
    long long bit = 1;
    while (p != 1 && p > 1) {
      bit++;
      p = p / 2;
    }
    long long dp[bit + 1];
    dp[1] = 1 % m;
    long long ans = 1 % m;
    for (long long i = 2; i <= bit; i++) {
      long long temp = pow(2, i - 1);
      if (i == bit) temp = d - temp + 1;
      dp[i] = (temp) % m;
      for (long long j = 1; j < i; j++) {
        dp[i] = (dp[i] + (temp * dp[j]) % m) % m;
      }
      ans = (ans + dp[i]) % m;
    }
    cout << ans << endl;
  }
}
