#include <bits/stdc++.h>   using namespace std;   long long n, m, q, k, v[300050], ans, d;   pair<long long, long long> w[300050];   string second;   int32_t main() {     ios::sync_with_stdio(false);     cin.tie(0);     cin >> q;     while (q--) {       cin >> d >> m;       if (d <= 3) {         if (d == 1)           cout << (1 % m) <<   n ;         else if (d == 2)           cout << 3 % m <<   n ;         else           cout << 5 % m <<   n ;       } else {         long long curr = 2, j = 1;         long long sum = 3, sum2 = 5;         while (1) {           long long ant = sum;           long long T = ((1LL << j) + 1) % m;           curr = (curr * T) % m;           if (sum <= d and d <= sum + (1LL << (j + 1))) {             long long falta = (d - ant) % m;             if (falta < 0) falta += m;             cout << (sum2 + falta * curr) % m <<   n ;             break;           }           sum += (1LL << (j + 1));           long long tam = (1LL << (j + 1)) % m;           sum2 = (sum2 + tam * curr) % m;           j++;         }       }     }   }   