#include <bits/stdc++.h>
using namespace std;
long long power(long long a, long long b) {
  long long ans = 1;
  while (b > 0) {
    if (b % 2 != 0) {
      ans = (ans * a) % 1000000007;
    }
    a = (a * a) % 1000000007;
    b >>= 1;
  }
  return ans;
}
int main() {
  std::ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  int t = 1;
  cin >> t;
  while (t--) {
    long long d, m;
    cin >> d >> m;
    vector<int> v, p, q;
    long long z = 1, s = 1;
    v.push_back(1);
    for (int i = 2; i < 65; i++) {
      long long k = pow(2, i - 1);
      if (s + k < d) {
        v.push_back(k);
        s += k;
      } else {
        v.push_back(d - s);
        break;
      }
    }
    vector<long long> ha;
    ha.push_back(1);
    ha.push_back(0);
    for (int i = 0; i < v.size(); i++) {
      vector<long long> u;
      u.push_back(1);
      for (int j = 0; j < ha.size() - 1; j++) {
        u.push_back((ha[j] * v[i] + ha[j + 1]) % m);
      }
      u.push_back(0);
      ha = u;
    }
    long long sum = 0;
    for (int i = 1; i < ha.size(); i++) {
      sum += ha[i];
      sum %= m;
    }
    cout << sum << endl;
  }
  return 0;
}
