#include <bits/stdc++.h>
using namespace std;
inline void using_file(string s) {
  freopen((s + ".in").c_str(), "r", stdin);
  freopen((s + ".out").c_str(), "w", stdout);
}
mt19937 gen_rand;
template <typename T, typename U>
ostream &operator<<(ostream &os, pair<T, U> &a) {
  os << "(";
  os << a.first << ", ";
  os << a.second;
  os << ")";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> &a) {
  os << "{";
  bool was = false;
  for (auto &x : a) {
    if (was) {
      os << ", ";
    }
    was = true;
    os << x;
  }
  os << "}";
  return os;
}
template <typename Head>
void debug(Head h) {
  cerr << h << "]" << endl;
}
template <typename Head, typename... Tail>
void debug(Head h, Tail... t) {
  cerr << h << ", ";
  debug(t...);
}
template <typename T>
T abs(T x) {
  if (x < 0) {
    return -x;
  } else {
    return x;
  }
}
template <typename T>
T sqr(T x) {
  return x * x;
};
const long long INF_FOR_SHORT_TIME = (long long)(1e9);
template <typename T>
T mul(T a, T b, T m) {
  if (a <= INF_FOR_SHORT_TIME && b <= INF_FOR_SHORT_TIME) {
    return (a * b) % m;
  }
  T q = (long long)((long double)a * (long double)b / (long double)m);
  T r = a * b - q * m;
  return (r + 5 * m) % m;
}
template <typename T, typename U>
T binpow(T a, U n, T MOD) {
  T res = 1;
  while (n) {
    if (n & 1) {
      res = mul(res, a, MOD);
    }
    a = mul(a, a, MOD);
    n >>= 1;
  }
  return res;
};
template <typename T>
int sign(T x) {
  if (x < 0) {
    return -1;
  } else if (x > 0) {
    return 1;
  } else {
    return 0;
  }
};
template <typename T>
T gcd(T a, T b) {
  if (a > b) {
    swap(a, b);
  }
  while (a) {
    b %= a;
    swap(a, b);
  }
  return b;
};
template <typename T>
bool uin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
};
template <typename T>
bool uax(T &a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
};
const long long max_bt = 40;
void solve() {
  long long d, m;
  cin >> d >> m;
  vector<vector<long long>> dp(max_bt, vector<long long>(max_bt, 0LL));
  long long res = 0;
  for (long long i = 0; i < max_bt; ++i) {
    long long x = (1LL << i);
    uax(dp[0][i], min(d - x + 1, x));
    dp[0][i] %= m;
    res += dp[0][i];
    res %= m;
  }
  for (long long i = 1; i < max_bt; ++i) {
    for (long long j = 0; j < max_bt; ++j) {
      long long cnt = 0;
      for (long long k = 0; k < j; ++k) {
        cnt += dp[i - 1][k];
        cnt %= m;
      }
      long long x = (1LL << j);
      if (d - x + 1 > 0) {
        dp[i][j] = cnt * min(d - x + 1, x);
        dp[i][j] %= m;
        res += dp[i][j];
        res %= m;
      }
    }
  }
  cout << res << "\n";
}
int main() {
  gen_rand.seed(time(0));
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int q;
  cin >> q;
  while (q--) {
    solve();
  }
  return 0;
}
