#include <bits/stdc++.h>
using namespace std;
long long msb[33];
void init() {
  msb[0] = 1;
  for (__typeof(33) i = (1) - ((1) > (33)); i != (33) - ((1) > (33));
       i += 1 - 2 * ((1) > (33))) {
    msb[i] = (1LL << (i));
  }
}
void solve() {
  long long n, m;
  cin >> n >> m;
  long long ms = log2(n);
  long long ans = 1;
  for (__typeof(ms) i = (0) - ((0) > (ms)); i != (ms) - ((0) > (ms));
       i += 1 - 2 * ((0) > (ms))) {
    long long t = (msb[i] + 1LL) % m;
    ans = (ans * t) % m;
  }
  long long rem = (n - ((1LL << ms) - 1)) % m;
  ans = (ans * (rem + 1LL)) % m;
  ans = (ans - 1 + m) % m;
  cout << ans << endl;
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long t = 1;
  init();
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}
