### 问题描述 小蓝是一位年轻的密码学家，他最近研究了一种新的加密算法——小桥加密。这个算法需要使用一个长度为 $n$ 的数组 $a$，其中每个元素都是 $1$ 到 $d$ 之间的整数。加密过程十分复杂，需要多次使用异或运算，具体流程如下： 1. 首先，将 $a$ 数组中的元素按照从小到大的顺序排序，得到一个新的数组 $a'$。 2. 然后，定义一个新的数组 $b$，令 $b_1=a'_1$。对于 $i>1$，$b_i$ 的值为 $b_{i-1}$ 和 $a'_i$ 之间的按位异或运算结果。 3. 最后，如果 $b$ 数组中的元素也是按照从小到大的顺序排序的，那么这个加密过程是有效的。 小蓝想知道，在保证加密过程有效的情况下，有多少种不同的 $a$ 数组可以用于小桥加密。由于结果可能非常大，你需要将答案对给定的模数进行取模。 ### 输入格式 第一行包含一个整数 $t$（$1\leq t \leq 100$），表示共有 $t$ 组测试数据。 接下来 $t$ 行，每行包含两个整数 $d$ 和 $m$（$1\leq d,m \leq 10^9$），含义如上文所述。 ### 输出格式 对于每组测试数据，输出一个整数，表示符合要求的 $a$ 数组的数量对 $m$ 取模的结果。 ### 样例输入 ``` 2 3 100000007 5 998244353 ``` ### 样例输出 ``` 5 17 ```