#include <bits/stdc++.h>
using namespace std;
namespace __SarcasticMonk {
template <typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
  cerr << name << " : " << arg1 << "\n";
}
template <typename Arg1, typename... Args>
void __f(const char *names, Arg1 &&arg1, Args &&...args) {
  const char *comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
long long mod = 1e9 + 7;
long long mod2 = 998244353;
const long long MAX = 1e6 + 204;
const long long MAX2 = 5009;
long long dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
long long ddx[8] = {1, 1, 0, -1, -1, -1, 0, 1},
          ddy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
template <typename T>
void amin(T &a, const T &b) {
  a = min(a, b);
}
template <typename T>
void amax(T &a, const T &b) {
  a = max(a, b);
}
template <typename T1, typename T2>
istream &operator>>(istream &in, pair<T1, T2> &a) {
  in >> a.fr >> a.sc;
  return in;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &out, pair<T1, T2> a) {
  out << a.fr << " " << a.sc;
  return out;
}
template <typename T>
struct is_outputtable {
  template <typename C>
  static constexpr decltype(declval<ostream &>() << declval<const C &>(),
                            bool())
  test(int32_t) {
    return true;
  }
  template <typename C>
  static constexpr bool test(...) {
    return false;
  }
  static constexpr bool value = test<T>(int32_t());
};
template <
    class T, typename V = decltype(declval<const T &>().begin()),
    typename S = typename enable_if<!is_outputtable<T>::value, bool>::type>
void pr(const T &x);
template <class T,
          typename V = decltype(declval<ostream &>() << declval<const T &>())>
void pr(const T &x) {
  cout << x;
}
template <class T1, class T2>
void pr(const pair<T1, T2> &x);
template <class Arg, class... Args>
void pr(const Arg &first, const Args &...rest) {
  pr(first);
  pr(rest...);
}
template <class T, bool pretty = false>
void prContain(const T &x) {
  if (pretty) pr("{");
  bool fst = 1;
  for (const auto &a : x) pr(!fst ? pretty ? " " : " " : "", a), fst = 0;
  if (pretty) pr("}");
}
template <class T>
void pc(const T &x) {
  prContain<T, false>(x);
  pr("\n");
}
template <class T1, class T2>
void pr(const pair<T1, T2> &x) {
  pr(x.first, " ", x.second, "\n");
}
template <class T, typename V, typename S>
void pr(const T &x) {
  prContain(x);
}
void ps() { pr("\n"); }
template <class Arg>
void ps(const Arg &first) {
  pr(first);
  ps();
}
template <class Arg, class... Args>
void ps(const Arg &first, const Args &...rest) {
  pr(first, " ");
  ps(rest...);
}
template <class T1, class T2>
void re(pair<T1, T2> &p);
template <class T>
void re(vector<T> &a);
template <class T, size_t SZ>
void re(array<T, SZ> &a);
template <class T>
void re(T &x) {
  cin >> x;
}
void re(double &x) {
  string t;
  re(t);
  x = stod(t);
}
template <class Arg, class... Args>
void re(Arg &first, Args &...rest) {
  re(first);
  re(rest...);
}
template <class T1, class T2>
void re(pair<T1, T2> &p) {
  re(p.first, p.second);
}
template <class T>
void re(vector<T> &a) {
  for (int32_t i = 0; i < (long long)a.size(); i++) re(a[i]);
}
template <class T, size_t SZ>
void re(array<T, SZ> &a) {
  for (int32_t i = 0; i < SZ; i++) re(a[i]);
}
long long binpow(long long a, long long b) {
  a %= mod;
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return res;
}
long long mul(long long a, long long b) { return (a % mod) * (b % mod) % mod; }
long long add(long long a, long long b) { return (a % mod + b % mod) % mod; }
long long sub(long long a, long long b) {
  return (a % mod - b % mod + mod) % mod;
}
long long divide(long long a, long long b) {
  return a * (long long)binpow(b, mod - 2) % mod;
}
}  // namespace __SarcasticMonk
using namespace __SarcasticMonk;
map<long long, long long> pos;
void fun(long long n) {
  for (long long i = 1; i <= log2(n) + 2; i++) {
    long long ma = pow(2, i) - 1;
    if (n >= ma) {
      pos[i] = binpow(2, i - 1);
    } else {
      long long cnt = n - (pow(2, i - 1) - 1);
      pos[i] = cnt;
      break;
    }
  }
}
void test_case(long long tc) {
  long long d, m;
  cin >> d >> m;
  mod = m;
  fun(d);
  long long ans = 0;
  long long n = 50;
  long long dp[60][60];
  for (long long i = 0; i <= 59; i++)
    for (long long j = 0; j <= 59; j++) dp[i][j] = 0;
  ;
  dp[0][0] = 1;
  for (long long j = 1; j <= n; j++) {
    for (long long bit = 1; bit <= log2(d) + 2; bit++) {
      for (long long k = bit - 1; k >= 0; k--) {
        dp[j][bit] = add(dp[j][bit], mul(pos[bit], dp[j - 1][k]));
      }
    }
  }
  long long cnt = 0;
  for (long long j = 1; j <= 50; j++) {
    for (long long k = 1; k <= 50; k++) {
      cnt = add(cnt, dp[j][k]);
    }
  }
  ans = add(ans, cnt);
  cout << ans << "\n";
  pos.clear();
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cout << fixed << setprecision(10);
  long long t = 1;
  cin >> t;
  for (long long i = 1; i <= t; i++) {
    test_case(i);
  }
}

### Prompt

Your task is to create 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;
namespace __SarcasticMonk {
template <typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
  cerr << name << " : " << arg1 << "\n";
}
template <typename Arg1, typename... Args>
void __f(const char *names, Arg1 &&arg1, Args &&...args) {
  const char *comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
long long mod = 1e9 + 7;
long long mod2 = 998244353;
const long long MAX = 1e6 + 204;
const long long MAX2 = 5009;
long long dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
long long ddx[8] = {1, 1, 0, -1, -1, -1, 0, 1},
          ddy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
template <typename T>
void amin(T &a, const T &b) {
  a = min(a, b);
}
template <typename T>
void amax(T &a, const T &b) {
  a = max(a, b);
}
template <typename T1, typename T2>
istream &operator>>(istream &in, pair<T1, T2> &a) {
  in >> a.fr >> a.sc;
  return in;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &out, pair<T1, T2> a) {
  out << a.fr << " " << a.sc;
  return out;
}
template <typename T>
struct is_outputtable {
  template <typename C>
  static constexpr decltype(declval<ostream &>() << declval<const C &>(),
                            bool())
  test(int32_t) {
    return true;
  }
  template <typename C>
  static constexpr bool test(...) {
    return false;
  }
  static constexpr bool value = test<T>(int32_t());
};
template <
    class T, typename V = decltype(declval<const T &>().begin()),
    typename S = typename enable_if<!is_outputtable<T>::value, bool>::type>
void pr(const T &x);
template <class T,
          typename V = decltype(declval<ostream &>() << declval<const T &>())>
void pr(const T &x) {
  cout << x;
}
template <class T1, class T2>
void pr(const pair<T1, T2> &x);
template <class Arg, class... Args>
void pr(const Arg &first, const Args &...rest) {
  pr(first);
  pr(rest...);
}
template <class T, bool pretty = false>
void prContain(const T &x) {
  if (pretty) pr("{");
  bool fst = 1;
  for (const auto &a : x) pr(!fst ? pretty ? " " : " " : "", a), fst = 0;
  if (pretty) pr("}");
}
template <class T>
void pc(const T &x) {
  prContain<T, false>(x);
  pr("\n");
}
template <class T1, class T2>
void pr(const pair<T1, T2> &x) {
  pr(x.first, " ", x.second, "\n");
}
template <class T, typename V, typename S>
void pr(const T &x) {
  prContain(x);
}
void ps() { pr("\n"); }
template <class Arg>
void ps(const Arg &first) {
  pr(first);
  ps();
}
template <class Arg, class... Args>
void ps(const Arg &first, const Args &...rest) {
  pr(first, " ");
  ps(rest...);
}
template <class T1, class T2>
void re(pair<T1, T2> &p);
template <class T>
void re(vector<T> &a);
template <class T, size_t SZ>
void re(array<T, SZ> &a);
template <class T>
void re(T &x) {
  cin >> x;
}
void re(double &x) {
  string t;
  re(t);
  x = stod(t);
}
template <class Arg, class... Args>
void re(Arg &first, Args &...rest) {
  re(first);
  re(rest...);
}
template <class T1, class T2>
void re(pair<T1, T2> &p) {
  re(p.first, p.second);
}
template <class T>
void re(vector<T> &a) {
  for (int32_t i = 0; i < (long long)a.size(); i++) re(a[i]);
}
template <class T, size_t SZ>
void re(array<T, SZ> &a) {
  for (int32_t i = 0; i < SZ; i++) re(a[i]);
}
long long binpow(long long a, long long b) {
  a %= mod;
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return res;
}
long long mul(long long a, long long b) { return (a % mod) * (b % mod) % mod; }
long long add(long long a, long long b) { return (a % mod + b % mod) % mod; }
long long sub(long long a, long long b) {
  return (a % mod - b % mod + mod) % mod;
}
long long divide(long long a, long long b) {
  return a * (long long)binpow(b, mod - 2) % mod;
}
}  // namespace __SarcasticMonk
using namespace __SarcasticMonk;
map<long long, long long> pos;
void fun(long long n) {
  for (long long i = 1; i <= log2(n) + 2; i++) {
    long long ma = pow(2, i) - 1;
    if (n >= ma) {
      pos[i] = binpow(2, i - 1);
    } else {
      long long cnt = n - (pow(2, i - 1) - 1);
      pos[i] = cnt;
      break;
    }
  }
}
void test_case(long long tc) {
  long long d, m;
  cin >> d >> m;
  mod = m;
  fun(d);
  long long ans = 0;
  long long n = 50;
  long long dp[60][60];
  for (long long i = 0; i <= 59; i++)
    for (long long j = 0; j <= 59; j++) dp[i][j] = 0;
  ;
  dp[0][0] = 1;
  for (long long j = 1; j <= n; j++) {
    for (long long bit = 1; bit <= log2(d) + 2; bit++) {
      for (long long k = bit - 1; k >= 0; k--) {
        dp[j][bit] = add(dp[j][bit], mul(pos[bit], dp[j - 1][k]));
      }
    }
  }
  long long cnt = 0;
  for (long long j = 1; j <= 50; j++) {
    for (long long k = 1; k <= 50; k++) {
      cnt = add(cnt, dp[j][k]);
    }
  }
  ans = add(ans, cnt);
  cout << ans << "\n";
  pos.clear();
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cout << fixed << setprecision(10);
  long long t = 1;
  cin >> t;
  for (long long i = 1; i <= t; i++) {
    test_case(i);
  }
}

```