#include <bits/stdc++.h>
using namespace std;
long long n, m, q, k, v[300050], ans, d;
pair<long long, long long> w[300050];
string second;
int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> q;
  while (q--) {
    cin >> d >> m;
    if (d <= 3) {
      if (d == 1)
        cout << (1 % m) << "\n";
      else if (d == 2)
        cout << 3 % m << "\n";
      else
        cout << 5 % m << "\n";
    } else {
      long long curr = 2, j = 1;
      long long sum = 3, sum2 = 5;
      while (1) {
        long long ant = sum;
        long long T = ((1LL << j) + 1) % m;
        curr = (curr * T) % m;
        if (sum <= d and d <= sum + (1LL << (j + 1))) {
          long long falta = (d - ant) % m;
          if (falta < 0) falta += m;
          cout << (sum2 + falta * curr) % m << "\n";
          break;
        }
        sum += (1LL << (j + 1));
        long long tam = (1LL << (j + 1)) % m;
        sum2 = (sum2 + tam * curr) % m;
        j++;
      }
    }
  }
}
