CF1329B.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 \lt a_2 \lt \dots \lt a_n \le d$
• Define an array $b$ of length $n$ as follows: $b_1 = a_1$, $\forall i \gt 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 \lt b_2 \lt \dots \lt b_{n - 1} \lt b_n$ should hold.

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

Dreamoon 非常喜欢序列，因此他构造了一个你在 OEIS 中找不到的关于序列的问题：

给你两个整数 $d, m$，求满足以下约束的数组 $a$ 的个数：

• 数组 $a$ 的长度为 $n$，其中 $n \ge 1$；
• $1 \le a_1 \lt a_2 \lt \dots \lt a_n \le d$；
• 定义一个长度为 $n$ 的数组 $b$ 如下：$b_1 = a_1$，且对所有 $i \gt 1$，有 $b_i = b_{i - 1} \oplus a_i$，其中 $\oplus$ 表示按位异或（xor）运算。在构造出数组 $b$ 后，需满足 $b_1 \lt b_2 \lt \dots \lt b_{n - 1} \lt b_n$。

由于可能的数组数量可能非常大，你只需输出答案对 $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!

第一行包含一个整数 $t$（$1 \leq t \leq 100$），表示输入中测试用例的数量。

接下来的 $t$ 行，每行包含两个整数 $d, m$（$1 \leq d, m \leq 10^9$）。

注意：$m$ 不一定是质数！

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

对于每个测试用例，输出满足所有给定约束条件的数组 $a$ 的数量对 $m$ 取模的结果。