#include <bits/stdc++.h>
#pragma warning(disable : 4996)
using namespace std;
template <typename T>
void print(vector<T>& a) {
  for (int i = 0; i < a.size(); i++) cout << a[i] << ' ';
  cout << "\n";
}
template <typename T>
void print(deque<T>& a) {
  for (int i = 0; i < a.size(); i++) cout << a[i] << ' ';
  cout << "\n";
}
template <typename T>
void print(vector<vector<T>>& a) {
  for (int i = 0; i < a.size(); i++) {
    for (int j = 0; j < a[i].size(); j++) cout << a[i][j] << ' ';
    cout << "\n";
  }
}
template <typename T>
void input(vector<T>& a) {
  for (int i = 0; i < a.size(); i++) cin >> a[i];
}
template <typename T>
void input(deque<T>& a) {
  for (int i = 0; i < a.size(); i++) cin >> a[i];
}
template <typename T>
void input(vector<vector<T>>& a) {
  for (int i = 0; i < a.size(); i++)
    for (int j = 0; j < a[i].size(); j++) cin >> a[i][j];
}
const long long INF = 1e9;
const long long MOD = 1e9 + 7;
const int NMAX = 1e3 + 17;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
void solve() {
  int d, m;
  cin >> d >> m;
  int d0 = d;
  int step = 0;
  int num1 = 0;
  long long ans = 0;
  while (d != 0) {
    if (d == 1) {
      ans += ((ans + 1) % m) * (((d0 ^ (1 << step)) + 1) % m) % m;
    } else {
      ans += ((ans + 1) % m) * ((1 << step) % m) % m;
    }
    step++;
    d = (d >> 1);
  }
  cout << ans % m << "\n";
}
int main() {
  srand(time(0));
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  while (t--) solve();
}
