#include <bits/stdc++.h>
using namespace std;
const int N = 50;
long long dp[N][N];
void work(int n, long long m) {
  for (int i = 1; i <= n; i++) dp[i][i] = 1;
  for (int b = 1; b <= n; b++) {
    for (int a = b - 1; a >= 1; a--) {
      dp[a][b] = 0;
      for (int i = a + 1; i <= b; i++) {
        dp[a][b] += (1ll << (i - 1)) * dp[i][b] % m;
        dp[a][b] %= m;
      }
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  int t;
  cin >> t;
  while (t--) {
    long long d, m;
    cin >> d >> m;
    int cnt = 0;
    long long td = d;
    while (td) {
      cnt++;
      td >>= 1;
    }
    work(cnt - 1, m);
    long long ans = 0;
    long long k = d - (1 << (cnt - 1)) + 1;
    for (int i = 1; i <= cnt - 1; i++) {
      for (int j = i; j <= cnt - 1; j++) {
        ans += (((1ll << (i - 1)) * dp[i][j] % m) * k) % m;
        ans %= m;
        ans += ((1ll << (i - 1)) * dp[i][j] % m) % m;
        ans %= m;
      }
    }
    cout << (ans + k) % m << endl;
  }
}
