#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 10;
int mod = 1e9 + 7;
int qpow(int a, int b) {
  int ans = 1;
  for (; b >= 1; b >>= 1, a = (long long)a * a % mod)
    if (b & 1) ans = (long long)ans * a % mod;
  return ans;
}
long long ans[32];
int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    int d, m, c;
    scanf("%d%d", &d, &mod);
    fill(ans, ans + 30, 0);
    for (c = 0; (1 << (c + 1)) <= d; c++)
      ;
    for (int i = 0; i < c; i++) ans[i] = (1ll << i) % mod;
    ans[c] = (d - (1ll << c) + 1) % mod;
    long long res = 1;
    for (int i = 0; i <= c; i++) res = res * (ans[i] + 1ll) % mod;
    res = (res + mod - 1) % mod;
    printf("%lld\n", res);
  }
  return 0;
}
