#include <bits/stdc++.h>
using namespace std;
void solve() {
  long long n, m, i, j, k;
  cin >> n >> m;
  long long x = 1, ans = 0;
  long long p = log2(n);
  p--;
  if (n == 1) {
    cout << n % m << "\n";
    return;
  }
  long long st = 1;
  x = 2;
  if (n == 2) {
    x = 1;
    long long y = 2 * st + 1;
    long long dif = y - st;
    st = y + (x - 1) * dif;
    cout << st % m << "\n";
    return;
  }
  while (p--) {
    long long y = 2 * st + 1;
    long long dif = y - st;
    st = y + (x - 1) * dif;
    st %= m;
    x *= 2;
  }
  x = n - x + 1;
  if (!x) {
    cout << st % m << endl;
    return;
  }
  long long y = 2 * st + 1;
  long long dif = y - st;
  st = y + (x - 1) * dif;
  st %= m;
  cout << st % m << "\n";
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long q = 1;
  cin >> q;
  while (q--) solve();
}
