為咗判斷有根樹係咪同構（喺呢題入面，你唔需要預先識得樹同構嘅背景知識），一種常見嘅算法係使用樹雜湊（tree hashing）。如果用咗合適嘅雜湊函數，唔同構嘅有根樹好大機會會得出唔同嘅雜湊值，但係雜湊碰撞亦都好難完全避免。

雜湊函數有各式各樣嘅實現方式，但有啲雜湊函數嘅設計並唔係咁正確。小 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