#include <bits/stdc++.h>
using namespace std;
long long t, d, m;
long long p;
long long ans;
signed main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  cin >> t;
  while (t--) {
    cin >> d >> m;
    p = 0;
    for (long long i = 2; i <= d; i *= 2) p++;
    ans = 0;
    for (long long i = 0; i < p; i++)
      ans = (ans + ans * (1 << i) + (1 << i)) % m;
    ans = (ans + ans * (d - (1 << p) + 1) + (d - (1 << p) + 1)) % m;
    cout << ans << endl;
  }
  return 0;
}
