A13276 | Dreamoon Likes Sequences

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 \ge 1$
- $1 \le a_1 < a_2 < \dots < a_n \le d$
- Define an array $b$ of length $n$ as follows: $b_1 = a_1$ , $\forall i > 1, b_i = b_{i - 1} \oplus a_i$ , where $\oplus$ is the bitwise exclusive-or (xor). After constructing an array $b$ , the constraint $b_1 < b_2 < \dots < 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$ .

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

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

Note that $m$ is not necessary the prime!

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