#include <bits/stdc++.h>
using namespace std;
long long int mpmod(long long int a, long long int b, long long int &mod) {
  a = a % mod;
  b = b % mod;
  a *= b;
  a = a % mod;
  return a;
}
void solve() {
  long long int d, m, prod = 1;
  long long int pow2 = 1;
  cin >> d >> m;
  if (m == 1) {
    cout << "0\n";
    return;
  }
  if (d == 1) {
    cout << "1\n";
    return;
  }
  while (pow2 * 2 <= d) {
    prod = mpmod(pow2 + 1, prod, m);
    pow2 *= 2;
  }
  d -= pow2;
  prod = (mpmod(prod, d + 2, m) - 1 + m) % m;
  cout << prod << endl;
}
int main() {
  int t;
  cin >> t;
  for (int i = 0; i < t; i++) solve();
}
