#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T>
using vec = vector<T>;
template <typename K, typename V>
using umap = unordered_map<K, V>;
template <typename K>
using uset = unordered_set<K>;
using vi = vec<int>;
using vl = vec<ll>;
using vpi = vec<pii>;
using vpl = vec<pll>;
using int128 = __int128_t;
using uint128 = __uint128_t;
template <typename I>
string intStr(I x) {
  string ret;
  while (x > 0) {
    ret += (x % 10) + '0';
    x /= 10;
  }
  reverse(ret.begin(), ret.end());
  return ret;
}
template <typename T>
inline void maxa(T& st, T v) {
  st = max(st, v);
}
template <typename T>
inline void mina(T& st, T v) {
  st = min(st, v);
}
inline void setprec(ostream& out, int prec) {
  out << setprecision(prec) << fixed;
}
template <typename T>
ostream& operator<<(ostream& out, vector<T> iter) {
  out << "[";
  for (auto t : iter) {
    out << t << ", ";
  }
  out << "]";
  return out;
}
template <typename T>
string arrayStr(T* arr, int sz) {
  string ret = "[";
  for (int i = 0; i < sz; i++) {
    ret += to_string(arr[i]) + ", ";
  }
  return ret + "]";
}
template <typename T>
void printArray(T* arr, int sz) {
  for (int i = 0; i < sz; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}
inline void scan() {}
template <typename F, typename... R>
inline void scan(F& f, R&... r) {
  cin >> f;
  scan(r...);
}
template <typename F>
inline void println(F t) {
  cout << t << '\n';
}
template <typename F, typename... R>
inline void println(F f, R... r) {
  cout << f << " ";
  println(r...);
}
inline void print() {}
template <typename F, typename... R>
inline void print(F f, R... r) {
  cout << f;
  print(r...);
}
template <typename F>
inline string __generic_tostring(F f) {
  stringstream ss;
  ss << f;
  return ss.str();
}
template <typename F>
inline string __join_comma(F f) {
  return __generic_tostring(f);
}
template <typename F, typename... R>
string __join_comma(F f, R... r) {
  return __generic_tostring(f) + ", " + __join_comma(r...);
}
ll MOD;
ll madd(ll a, ll b) { return (a + b) % MOD; }
ll msub(ll a, ll b) { return (a - b + MOD) % MOD; }
ll mmul(ll a, ll b) { return (a * b) % MOD; }
ll fpow(ll x, ll y) {
  if (!y) return 1LL;
  return mmul(fpow(mmul(x, x), y >> 1), (y & 1) ? x : 1LL);
}
ll D;
void solve() {
  int lg = 0;
  while ((1LL << lg) <= D) lg++;
  lg--;
  vl dp(lg + 1);
  dp[0] = 2LL;
  for (__typeof(1) i = 1; i < lg + 1; i++) {
    ll cnt = min(D, (1LL << (i + 1)) - 1) - (1LL << i) + 1;
    dp[i] = madd(mmul(cnt, dp[i - 1]), dp[i - 1]);
  }
  println(msub(dp.back(), 1));
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int T;
  cin >> T;
  while (T--) {
    scan(D, MOD);
    solve();
  }
}

### Prompt

Your challenge is to write a cpp solution to the following problem:

Dreamoon likes sequences very much. So he created a problem about the sequence that you can't find in OEIS: 

You are given two integers d, m, find the number of arrays a, satisfying the following constraints:

  * The length of a is n, n ≥ 1 
  * 1 ≤ a_1 < a_2 < ... < a_n ≤ d 
  * Define an array b of length n as follows: b_1 = a_1, ∀ i > 1, b_i = b_{i - 1} ⊕ a_i, where ⊕ is the bitwise exclusive-or (xor). After constructing an array b, the constraint b_1 < b_2 < ... < b_{n - 1} < b_n should hold. 



Since the number of possible arrays may be too large, you need to find the answer modulo m.

Input

The first line contains an integer t (1 ≤ t ≤ 100) denoting the number of test cases in the input.

Each of the next t lines contains two integers d, m (1 ≤ d, m ≤ 10^9).

Note that m is not necessary the prime!

Output

For each test case, print the number of arrays a, satisfying all given constrains, modulo m.

Example

Input


10
1 1000000000
2 999999999
3 99999998
4 9999997
5 999996
6 99995
7 9994
8 993
9 92
10 1


Output


1
3
5
11
17
23
29
59
89
0

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T>
using vec = vector<T>;
template <typename K, typename V>
using umap = unordered_map<K, V>;
template <typename K>
using uset = unordered_set<K>;
using vi = vec<int>;
using vl = vec<ll>;
using vpi = vec<pii>;
using vpl = vec<pll>;
using int128 = __int128_t;
using uint128 = __uint128_t;
template <typename I>
string intStr(I x) {
  string ret;
  while (x > 0) {
    ret += (x % 10) + '0';
    x /= 10;
  }
  reverse(ret.begin(), ret.end());
  return ret;
}
template <typename T>
inline void maxa(T& st, T v) {
  st = max(st, v);
}
template <typename T>
inline void mina(T& st, T v) {
  st = min(st, v);
}
inline void setprec(ostream& out, int prec) {
  out << setprecision(prec) << fixed;
}
template <typename T>
ostream& operator<<(ostream& out, vector<T> iter) {
  out << "[";
  for (auto t : iter) {
    out << t << ", ";
  }
  out << "]";
  return out;
}
template <typename T>
string arrayStr(T* arr, int sz) {
  string ret = "[";
  for (int i = 0; i < sz; i++) {
    ret += to_string(arr[i]) + ", ";
  }
  return ret + "]";
}
template <typename T>
void printArray(T* arr, int sz) {
  for (int i = 0; i < sz; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}
inline void scan() {}
template <typename F, typename... R>
inline void scan(F& f, R&... r) {
  cin >> f;
  scan(r...);
}
template <typename F>
inline void println(F t) {
  cout << t << '\n';
}
template <typename F, typename... R>
inline void println(F f, R... r) {
  cout << f << " ";
  println(r...);
}
inline void print() {}
template <typename F, typename... R>
inline void print(F f, R... r) {
  cout << f;
  print(r...);
}
template <typename F>
inline string __generic_tostring(F f) {
  stringstream ss;
  ss << f;
  return ss.str();
}
template <typename F>
inline string __join_comma(F f) {
  return __generic_tostring(f);
}
template <typename F, typename... R>
string __join_comma(F f, R... r) {
  return __generic_tostring(f) + ", " + __join_comma(r...);
}
ll MOD;
ll madd(ll a, ll b) { return (a + b) % MOD; }
ll msub(ll a, ll b) { return (a - b + MOD) % MOD; }
ll mmul(ll a, ll b) { return (a * b) % MOD; }
ll fpow(ll x, ll y) {
  if (!y) return 1LL;
  return mmul(fpow(mmul(x, x), y >> 1), (y & 1) ? x : 1LL);
}
ll D;
void solve() {
  int lg = 0;
  while ((1LL << lg) <= D) lg++;
  lg--;
  vl dp(lg + 1);
  dp[0] = 2LL;
  for (__typeof(1) i = 1; i < lg + 1; i++) {
    ll cnt = min(D, (1LL << (i + 1)) - 1) - (1LL << i) + 1;
    dp[i] = madd(mmul(cnt, dp[i - 1]), dp[i - 1]);
  }
  println(msub(dp.back(), 1));
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int T;
  cin >> T;
  while (T--) {
    scan(D, MOD);
    solve();
  }
}

```