Dreamoon非常喜欢序列。所以他创造了一个关于序列的问题,你在 OEIS 中找不到:
给定两个整数$$$d, m$$$,求数组$$$a$$$的个数,满足以下约束:
- $$$a$$$ 的长度为 $$$n$$$, $$$n \ge 1$$$
- $$$1 \le a_1 < a_2 < \dots < a_n \le d$$$
- 定义长度为 $$$n$$$ 的数组 $$$b$$$,如下所示: $$$b_1 = a_1$$$, $$$\forall i > 1, b_i = b_{i - 1} \oplus a_i$$$,其中 $$$\oplus$$$ 是按位异或 (xor)。构造数组 $$$b$$$ 后,约束 $$$b_1 < b_2 < \dots < b_{n - 1} < b_n$$$ 应该成立。
由于可能的数组数量可能太大,您需要对 $$$m$$$ 求模答案。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$) 表示输入中测试用例的数量。
接下来的 $$$t$$$ 行包含两个整数 $$$d, m$$$ ($$$1 \leq d, m \leq 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
1 3 5 11 17 23 29 59 89 0