#include <bits/stdc++.h>
using namespace std;
const int maxn = 33;
const int maxm = 100;
const int inf = 2147483647;
const double eps = 1e-9;
const long long INF = 9223372036854775807ll;
long long qpow(long long a, long long b, long long c) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans = ans * a % c;
    a = a * a % c;
    b >>= 1;
  }
  return ans;
}
long long dp[maxn][maxn];
int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    int d, m;
    scanf("%d%d", &d, &m);
    int k;
    for (register int i = (0); i < (32); ++i) {
      if (((1 << i) - 1) >= d) {
        k = i;
        break;
      }
    }
    memset(dp, 0, sizeof(dp));
    for (register int i = (0); i < (k + 1); ++i) dp[i][0] = 1;
    for (register int i = (1); i < (k + 1); ++i)
      for (register int j = (1); j < (k + 1); ++j) {
        if (i != k)
          dp[i][j] = (dp[i - 1][j - 1] * (long long)(1 << (i - 1)) % m +
                      dp[i - 1][j]) %
                     m;
        else if (i == 1)
          dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % m;
        else
          dp[i][j] =
              (dp[i - 1][j - 1] * (long long)(d - (1 << (i - 1)) + 1) % m +
               dp[i - 1][j]) %
              m;
      }
    long long ans = 0;
    for (register int i = (1); i < (k + 1); ++i) ans = (ans + dp[k][i]) % m;
    printf("%lld\n", ans);
  }
}
