#include <bits/stdc++.h>
const long long mod = 1e9 + 7;
const long long N = 1e5 + 5;
const int max_ = 1e5 + 5;
const double eps = 1e-7;
using namespace std;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
long long lcm(long long a, long long b) { return a * b / gcd(a, b); }
long long qp(long long a, long long b, long long p) {
  long long ans = 1;
  while (b) {
    if (b & 1) {
      ans = (ans * a) % p;
      --b;
    }
    a = (a * a) % p;
    b >>= 1;
  }
  return ans % p;
}
long long Inv(long long x) { return qp(x, mod - 2, mod); }
long long C(long long n, long long m) {
  if (m > n) return 0;
  long long ans = 1;
  for (int i = 1; i <= m; ++i) ans = ans * Inv(i) % mod * (n - i + 1) % mod;
  return ans % mod;
}
long long f[32];
int main() {
  f[0] = 1;
  for (int i = 1; i <= 31; i++) f[i] = f[i - 1] * 2;
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  long long t;
  cin >> t;
  while (t--) {
    long long d, m, i, cnt = 0, ans = 1;
    cin >> d >> m;
    for (i = 0; d >= f[i]; i++)
      ;
    cnt = d - f[i - 1] + 1;
    for (long long j = 0; j <= i - 2; j++) ans = ans * (f[j] + 1) % m;
    ans = (ans) * (cnt + 1) % m;
    cout << (ans - 1 + m) % m << endl;
  }
  return 0;
}
