#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
const int inf = 0x3f3f3f3f;
const int N = 35;
template <typename T>
void chkmax(T &x, T y) {
  x = max(x, y);
}
template <typename T>
void chkmin(T &x, T y) {
  x = min(x, y);
}
long long qpow(long long x, long long y, long long MOD) {
  long long a = 1;
  while (y) {
    if (y & 1) a = a * x % MOD;
    x = x * x % MOD;
    y >>= 1;
  }
  return a;
}
long long d, mod;
int a[N];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int T;
  cin >> T;
  while (T--) {
    cin >> d >> mod;
    int cnt = 0;
    for (int i = int(0); i <= int(30); ++i) {
      if (d >= (1 << i)) a[++cnt] = (1 << i);
    }
    long long ans = 1;
    for (int i = int(2); i <= int(cnt); ++i)
      ans = ans * (a[i] - a[i - 1] + 1) % mod;
    ans = ans * (d - a[cnt] + 2) % mod;
    ans = (ans - 1 + mod) % mod;
    cout << ans << endl;
  }
  return 0;
}
