根付き木が同型であるかどうかを判定するために（この問題では、木の同型に関する予備知識は必要ありません）、木ハッシュ（tree hashing）を用いるアルゴリズムがよく知られています。適切なハッシュ関数を用いれば、同型でない根付き木は異なるハッシュ値を持つ可能性が高くなりますが、ハッシュの衝突を避けることもまた困難です。

ハッシュ関数にはさまざまな実装がありますが、中にはあまり正しくない設計のハッシュ関数もあります。Little C は次のような「あまり正しくない」ハッシュ関数を持っています。頂点 $x$ の部分木に含まれる頂点の個数を $sz_x$ とし、$x$ のすべての子頂点からなる集合を $son_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つだけの根付き木のハッシュ値は $1$ です。

次に Little C は、2つの根付き木について、どのように $f$ を選んでも異なるハッシュ値を計算することが不可能であるとき、その2つの木は区別不能（indistinguishable）であると定義します。逆に、2つの木で異なるハッシュ値が計算できるような $f$ の選び方が存在するとき、その2つの木は区別可能（distinguishable）であると定義します。

Little C はこのハッシュ関数を用いて、できるだけ多くの根付き二分木（各頂点が最大で2つの子頂点を持つ根付き木）を生成したいと考えています。Little C は、$n$ 個の頂点を含む互いに区別可能な根付き二分木の最大個数をあなたに計算してほしいと願っています。もちろん答えは非常に大きくなる可能性があるため、Little C は法 $p$ を用意しました。答えを $p$ で割った余りを求めてください。

入力

この問題は複数のテストケースを含みます。入力の最初の行には、テストケースの個数を表す整数 $T$（$1 \le T \le 10000$）が含まれます。

各テストケースについて、入力は2つの整数 $n, p$（$1 \le n \le 3000, 2 \le p \le 10^9 + 9$）が書かれた単一の行からなり、それぞれ根付き木の頂点数と Little C が用意した法を表します。

すべてのテストケースにおける $n$ の総和が $10000$ を超えないことが保証されています。

出力

各テストケースについて、答えを $p$ で割った余りを表す整数を1行に出力してください。

入出力例

入力例 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