為了判斷有根樹是否同構（在本題中，你不需要具備樹同構的先備知識），一種常見的演算法是使用樹雜湊（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