#include <bits/stdc++.h>
using namespace std;
const long long N = 1e5 + 10;
long long f[N];
inline long long fp(long long a, long long n, long long m) {
  long long res = 1;
  while (n) {
    if (n & 1) res = (res * a) % m;
    a = (a * a) % m;
    n >>= 1;
  }
  return res % m;
}
signed main() {
  long long T;
  cin >> T;
  while (T--) {
    long long d, m;
    cin >> d >> m;
    long long k = 0;
    while ((1 << k) <= d) {
      k++;
    }
    k--;
    memset(f, 0, sizeof(f));
    f[0] = 1;
    for (long long i = 1; i <= k; i++) {
      if (i != k)
        f[i] = (f[i - 1] + (f[i - 1] * fp(2, i, m) % m) + fp(2, i, m)) % m;
      else
        f[i] = (f[i - 1] + (f[i - 1] * (d - fp(2, k, m) + 1) % m) +
                (d - fp(2, k, m) + 1)) %
               m;
    }
    cout << f[k] % m << endl;
  }
}
