Dreamoon Likes Sequences

### 题目描述 Dreamoon 非常喜欢数列。因此他出了一道数列问题，保证你在 OEIS 上找不到它。 有两个整数 $d, m$，找到这样的数列 $a$ 的数列，满足以下限制条件： - 数列 $a$ 的长度为 $n$，$n \ge 1$； - $1 \le a_i \lt a_2 \lt \cdots \lt a_n \le d$； - 定义一个长度为 $n$ 的数组 $b$：$b_1 = a_1$，$\forall i \ge 1, b_i = b_{i - 1} \oplus a_i$，其中 $\oplus$ 表示二进制异或 (xor)。在构建出 $b$ 后，应当满足 $b_1 \lt b_2 \lt \cdots \lt b_{n - 1} \lt b_n$ 的限制条件。 由于满足条件的数列数量可能很多，请输出答案模 $m$ 的结果。 ### 输入格式 第一行输入一个整数 $t ~ (1 \le t \le 100)$，表示测试数据组数。 接下来 $t$ 行，每行输入两个整数 $d, m ~ (1 \le d, m \le 10 ^ 9)$。 注意 $m$ 不一定是一个质数！ ### 输出格式 对于每组测试数据，输出满足条件的数列 $a$ 的个数，对 $m$ 取模的结果。

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 $ .

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

1
3
5
11
17
23
29
59
89
0