#include <bits/stdc++.h>
using namespace std;
const long long int N = 300005;
long long int d, M;
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  long long int tt;
  cin >> tt;
  while (tt--) {
    vector<long long int> a;
    cin >> d >> M;
    for (long long int bit = 0; bit <= 30; ++bit) {
      long long int from = 1LL << bit;
      long long int to = min(d, (1LL << (bit + 1)) - 1);
      if (from <= to) {
        a.push_back(to - from + 1);
      }
    }
    long long int n = a.size();
    vector<long long int> dp(n, 0);
    for (long long int i = 0; i < n; ++i) {
      dp[i] = a[i];
      for (long long int j = 0; j < i; ++j) {
        dp[i] = (dp[i] + (a[i] * dp[j]) % M) % M;
      }
    }
    long long int res = 0;
    for (long long int i = 0; i < n; ++i) res = (res + dp[i]) % M;
    cout << res << '\n';
  }
  return 0;
}
