### 问题描述 丽丽最近研究了一种新的数据压缩算法，这个算法需要使用一个长度为 $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^3$），含义如上文所述。 ### 输出格式 对于每组测试数据，输出一个整数，表示符合要求的 $a$ 数组的数量对 $m$ 取模的结果。 ### 样例输入 ``` 2 3 100000007 5 998244353 ``` ### 样例输出 ``` 5 17 ```