#include <bits/stdc++.h>
using namespace std;
const int INF = 2147483647;
const int INF2 = 0x3f3f3f3f;
const long long INF64 = 1e18;
const double INFD = 1e30;
const double EPS = 1e-9;
const double PI = acos(-1);
const int MOD = 998244353;
template <typename T>
inline T read() {
  T X = 0, w = 0;
  char ch = 0;
  while (!isdigit(ch)) {
    w |= ch == '-';
    ch = getchar();
  }
  while (isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
  return w ? -X : X;
}
const int MAXN = 20005;
int n, m, k;
int dr[4] = {1, 0, -1, 0};
int dc[4] = {0, 1, 0, -1};
int dr2[8] = {1, 1, 1, -1, -1, -1, 0, 0};
int dc2[8] = {1, 0, -1, 1, 0, -1, 1, -1};
int CASE = 1;
template <typename T>
struct List {
  T* data;
  int sz;
  List() : data(nullptr), sz(0) {}
  ~List() {
    if (data) delete data;
  }
};
bool vis[MAXN];
vector<int> primes;
void sieve(int x) {
  for (int i = 2; i * i <= x; i++) {
    if (vis[i]) continue;
    for (int j = i * i; j <= x; j += i) {
      vis[j] = true;
    }
  }
}
void getprimes(int x) {
  sieve(x);
  for (int i = 2; i <= x; i++) {
    if (!vis[i]) primes.push_back(i);
  }
}
void solve() {
  scanf("%d%d", &n, &m);
  if (n == 1) {
    printf("%d\n", 1 % m);
    return;
  }
  long long ans = 1;
  ++n;
  long long i = 1;
  for (; (1 << i) < n; i++) {
    ans = (ans * ((1 << (i - 1)) + 1)) % m;
  }
  ans = (ans * (n - (1 << (i - 1)) + 1)) % m;
  printf("%lld\n", (ans + m - 1) % m);
}
int main() {
  int T = read<int>();
  while (T--) {
    solve();
  }
  return 0;
}
