#include <bits/stdc++.h>
using namespace std;
const int SIZE = 50;
long long li[SIZE];
long long dp[SIZE][SIZE];
int main(void) {
  int test;
  scanf("%d", &test);
  while (test--) {
    int d, m;
    scanf("%d%d", &d, &m);
    int cnt = 0;
    for (long long xpow = 1; d; xpow <<= 1) {
      li[++cnt] = min(xpow, (long long)d);
      d -= li[cnt];
    }
    memset(dp, 0, sizeof dp);
    dp[0][0] = 1 % m;
    for (register int i = 1; i <= cnt; ++i) {
      dp[i][0] = 1 % m;
      for (register int j = 1; j <= i; ++j)
        dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1] * li[i]) % m;
    }
    long long ans = 0;
    for (register int i = 1; i <= cnt; ++i) ans = (ans + dp[cnt][i]) % m;
    printf("%lld\n", ans);
  }
  return 0;
}
