#include <bits/stdc++.h>
using namespace std;
long long min(long long a, long long b) { return a > b ? b : a; }
long long max(long long a, long long b) { return a > b ? a : b; }
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  long long t;
  cin >> t;
  while (t--) {
    long long d, m;
    cin >> d >> m;
    if (d == 1) {
      cout << d % m << "\n";
      continue;
    }
    long long lol = d;
    long long n = -1;
    while (lol) {
      n++;
      lol /= 2;
    }
    long long ans = 1;
    for (long long i = 1; i < n; i++) {
      long long cur = (1 << (i + 1)) - (1 << i);
      cur %= m;
      ans = ans + cur + ans * cur;
      ans %= m;
    }
    long long cur = d - (1 << (n)) + 1;
    cur %= m;
    ans = ans + cur + ans * cur;
    cout << ans % m << "\n";
  }
  return 0;
}
