#include <bits/stdc++.h>
using namespace std;
const int64_t inf = 1e17;
const int64_t MOD = 998244353;
int64_t inp() {
  int64_t x;
  cin >> x;
  return x;
}
string inp_str() {
  string x;
  cin >> x;
  return x;
}
int64_t sqr(int64_t n) { return n * n; }
int64_t power(int64_t a, int64_t b, int64_t mod = MOD) {
  int64_t res = 1;
  a %= mod;
  for (int64_t i = (0); i <= (log2(b)); ++i) {
    if (b & (1 << i)) res = (res * a) % mod;
    a = (a * a) % mod;
  }
  return res;
}
int64_t gcd(int64_t a, int64_t b) {
  while (b > 0) {
    int64_t tmp = a % b;
    a = b;
    b = tmp;
  }
  return a;
}
bool is_pal(string s) { return equal((s).begin(), (s).end(), s.rbegin()); }
void fast_io() {
  ios::sync_with_stdio(0);
  cin.tie(0);
}
void file_io(string in, string out) {
  freopen(in.c_str(), "r", stdin);
  freopen(out.c_str(), "w", stdout);
}
int64_t d, m;
vector<int64_t> dp(32, 1);
vector<int64_t> pow2(32, 1);
void Input() {
  d = inp(), m = inp();
  dp[0] = 1;
  pow2[0] = 1;
  for (int64_t i = (1); i <= (dp.size() - 1); ++i) {
    pow2[i] = (pow2[i - 1] * 2) % m;
    dp[i] = (dp[i - 1]) * ((pow2[i] - pow2[i - 1] + 1) % m) % m;
  }
}
void Solve() {
  int64_t k = log2(d);
  int64_t ans = (dp[k] * (d % m - pow2[k] % m + 2) % m - 1) % m;
  if (ans < 0) ans += m;
  cout << ans << "\n";
}
int main() {
  fast_io();
  int64_t t = inp();
  while (t--) Input(), Solve();
  return 0;
}
