题目描述

小王很喜欢数列问题，他觉得数列问题十分简单，于是决定出道数列问题来考一考你

有两个整数 $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$ 取模的结果。

样例 #1

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