#include <bits/stdc++.h>
using namespace std;
long long t, d, m, k;
long long add(long long x, long long y) { return (x + y) % m; }
long long mul(long long x, long long y) { return x * y % m; }
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> t;
  while (t--) {
    cin >> d >> m;
    long long ans = 1;
    for (long long i = 0; i < 35; i++) {
      k = max(0ll, min((1ll << i + 1) - (1ll << i), d + 1 - (1ll << i)));
      k++;
      ans = mul(ans, k);
    }
    ans = add(ans, m - 1);
    cout << ans << endl;
  }
}
