#include <bits/stdc++.h>
using namespace std;
long long t, d, m, high;
long long func(long long);
int main() {
  scanf("%lld", &t);
  while (t--) {
    scanf("%lld %lld", &d, &m);
    high = 0;
    while (d >= (1ll << high)) high++;
    high--;
    printf("%lld\n", (func(0) - 1 + m) % m);
  }
}
long long func(long long bit) {
  if (bit == high) return ((d ^ (1 << high)) + 2) % m;
  if (bit == 0) return (2 * func(bit + 1)) % m;
  return (((1ll << bit) + 1) * func(bit + 1)) % m;
}
