为了判断有根树是否同构（在本题中，你不需要具备树同构的先验知识），一种常见的算法是使用树哈希。通过合适的哈希函数，非同构的有根树很可能产生不同的哈希值，但哈希冲突也很难避免。
哈希函数有各种实现方式，但某些哈希函数的设计并不完全正确。小 C 有一个这样的“不太正确”的哈希函数，定义如下：令 $sz_x$ 为以 $x$ 为根的子树中包含的节点数， $son_x$ 为 $x$ 的所有子节点的集合。对于一棵以 $r$ 为根的有根树，其哈希值 $h(r)$ 定义为：
$$ h(r) = 1 + \sum_{v \in son_r} h(v) \times f(sz_v) $$
其中 $f$ 表示从正整数集到正整数集的任意映射，即 $f \in \{ \varphi : \mathbb{Z}^+ \to \mathbb{Z}^+ \}$ 。特别地，仅包含一个节点的有根树的哈希值为 $1$。
接下来，小 C 定义，对于两棵有根树，如果在 $f$ 的所有选择下，都不可能计算出不同的哈希值，则称这两棵树是不可区分的；否则，如果存在一种 $f$ 的选择，使得这两棵树可以计算出不同的哈希值，则称这两棵树是可区分的。
小 C 希望利用这个哈希函数生成尽可能多的有根二叉树（即每个节点最多有两个子节点的有根树）。小 C 希望你能计算出包含 $n$ 个节点的、彼此可区分的有根二叉树的最大数量。当然，答案可能很大，因此小 C 为你准备了一个模数 $p$ ，你需要将结果对 $p$ 取模。
输入格式
本题包含多个测试用例。输入的第一行包含一个整数 $T ( 1 \le T \le 10000 )$，表示测试用例的数量。
对于每个测试用例，输入包含一行，包含两个整数 $n, p ( 1 \le n \le 3000 , 2 \le p \le 10^9+9 )$，分别表示有根树的节点数和小 C 提供的模数。
保证所有测试用例的 $n$ 之和不超过 $10000$。
输出格式
对于每个测试用例，输出一行一个整数，表示答案对 $p$ 取模的结果。
样例
样例输入 $1$
8
1 1000000009
5 1000000009
10 1000000009
15 1000000009
100 1000000009
150 1000000009
1000 1000000009
1500 1000000009样例输出 $1$
1
6
207
10904
478868953
202933416
152259136
264735211