#include <bits/stdc++.h>
using namespace std;
long long int get_msb(long long int num) {
  long long int msb = 0;
  while (num / 2 != 0) {
    msb += 1;
    num /= 2;
  }
  return msb;
}
int main() {
  long long int t;
  cin >> t;
  for (long long int i = 0; i < t; i++) {
    long long int d, m;
    cin >> d >> m;
    long long int ans = 1;
    long long int MSB = get_msb(d);
    for (long long int j = 0; j < MSB; j++) {
      ans = (ans * (long(pow(2, j)) % m + 1) % m) % m;
    }
    long long int last_extra_nums = (d & (long(pow(2, MSB)) - 1)) + 2;
    ans = (ans * last_extra_nums % m) % m;
    cout << (((ans - 1) % m) + m) % m << endl;
  }
}
