数列

题目描述

小琪非常喜欢数列，因此她出了一道数列问题。

有两个整数 $d,m$ ，找到这样的数列 $a$, 满足如下条件

• 数列 $a$ 的长度为 $n, n \ge 1$
• $1 \le a_1 < a_2 < \quad ... \quad < a_n \le d$
• 定义数组一个长度为 $n$ 的数组 $c$：$c_1 = a_1$ , $\forall i > 1, c_i = c_{i-1} \oplus a_i$ , $\oplus$ 表示二进制异或 。数组 $c$ 应该满足 $c_1 < c_2 < \quad ... \quad < c_n$ 的限制条件

请你求出满足条件的数列有多少个？由于结果较大，请输出答案模 $m$ 的结果

输入格式

第一行一个数字 $\quad t \quad (1 \le t \le 100)$ ，表示测试数据数

接下来 $t$ 行，每行 $2$ 个整数 $\quad d, m \quad (1 \le d, m \le 10^9)$

注意: $m$ 不一定是质数

输出格式

输出包括 $t$ 行，每行一个整数表示答案

样例输入

3
5 999996
6 99995
7 9994

样例输出

17
23
29

数据范围

所有数据保证 $1\leq t \leq 100, 1 \leq d,m \leq 10^9$