#include <bits/stdc++.h>
using namespace std;
long long mod = 1e9 + 7;
vector<long long> fact(10005);
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long power(long long x, long long y) {
  long long temp;
  if (y == 0) return 1;
  temp = power(x, y / 2);
  if (y % 2 == 0)
    return temp * temp;
  else
    return x * temp * temp;
}
long long power(long long x, long long y, long long p) {
  long long res = 1;
  x = x % p;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
long long modInv(long long n, long long p) { return power(n, p - 2, p); }
long long ncr(long long n, long long r) {
  return (n >= r ? (fact[n] * modInv(fact[r], mod)) % mod *
                       modInv(fact[n - r], mod) % mod
                 : 0);
}
long long add(long long a, long long b) {
  long long z = a + b;
  if (z >= mod) z -= mod;
  return z;
}
long long mul(long long a, long long b) { return (a * b) % mod; }
long long sub(long long a, long long b) { return (a - b + mod) % mod; }
int main() {
  long long t = 1, n, i, j, m, cnt, f, ff;
  cin >> t;
  while (t--) {
    cin >> n >> mod;
    long long z = log2(n) - 1;
    long long ans = (n - (1 << (z + 1)) + 2) % mod;
    for (i = 0; i <= z; i++) {
      ans = mul(ans, (1 << i) + 1);
    }
    if (ans == 0)
      cout << mod - 1 << '\n';
    else
      cout << ans - 1 << '\n';
  }
}
