#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  register long long x = 0;
  register bool f = 0;
  register char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = 1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = (x << 3) + (x << 1) + c - 48;
    c = getchar();
  }
  return f ? -x : x;
}
char cr[200];
long long tt;
inline void print(register long long x, register char k = '\n') {
  if (!x) putchar('0');
  if (x < 0) putchar('-'), x = -x;
  while (x) cr[++tt] = x % 10 + '0', x /= 10;
  while (tt) putchar(cr[tt--]);
  putchar(k);
}
long long pw[50], t, d, p, f[50], g[50];
signed main() {
  t = read();
  while (t--) {
    pw[0] = 1;
    d = read() - 1;
    p = read();
    for (long long i = 1; i <= 40; i++) {
      pw[i] = pw[i - 1] * 2;
    }
    f[0] = 3;
    for (long long i = 1; i <= 40; i++) {
      f[i] = (f[i - 1] + pw[i]) % p;
    }
    g[1] = 2;
    for (long long i = 2; i <= 40; i++) {
      g[i] = (g[i - 1] * f[i - 2]) % p;
    }
    long long ans = 1 % p;
    if (d == 0) {
      print(ans);
      continue;
    }
    for (long long i = 1; i <= 40; i++) {
      if (d < pw[i]) {
        ans = (ans + d % p * g[i] % p) % p;
        break;
      } else {
        ans = (ans + pw[i] % p * g[i] % p) % p;
        d -= pw[i];
      }
    }
    print(ans % p);
  }
}
