För att avgöra om rotade träd är isomorfa (i detta problem behöver du inga förkunskaper om trädisomorfi) är en vanlig algoritm att använda trädhashning (tree hashing). Med en lämplig hashfunktion ger icke-isomorfa rotade träd sannolikt olika hashvärden, men hashkollisioner är samtidigt svåra att undvika.

Det finns olika implementationer av hashfunktioner, men vissa konstruktioner av hashfunktioner är inte särskilt korrekta. Lilla C har en sådan ”inte särskilt korrekt” hashfunktion, definierad enligt följande: Låt $sz_x$ vara antalet noder i delträdet till $x$, och låt $son_x$ vara mängden av alla barnnoder till $x$. För ett rotat träd med $r$ som rot definieras dess hashvärde $h(r)$ som:

$$h(r) = 1 + \sum_{v \in son_r} h(v) \times f(sz_v)$$

där $f$ representerar en godtycklig avbildning från mängden av positiva heltal till mängden av positiva heltal, det vill säga $f \in \{\varphi : \mathbb{Z}^+ \to \mathbb{Z}^+\}$. Speciellt är hashvärdet för ett rotat träd med endast en nod lika med $1$.

Därefter definierar Lilla C att för två rotade träd gäller följande: om det för alla val av $f$ är omöjligt att beräkna olika hashvärden, sägs de två träden vara oskiljbara; annars, om det finns ett val av $f$ sådant att de två träden kan ge olika hashvärden, sägs de två träden vara skiljbara.

Lilla C vill använda denna hashfunktion för att generera så många rotade binära träd som möjligt, det vill säga rotade träd där varje nod har högst två barnnoder. Lilla C hoppas att du kan beräkna det maximala antalet parvis skiljbara rotade binära träd som innehåller $n$ noder. Eftersom svaret förstås kan bli mycket stort har Lilla C förberett en modul $p$ åt dig, och du ska ange ditt resultat modulo $p$.

Indata

Detta problem innehåller flera testfall. Den första raden i indatan innehåller ett heltal $T$ ($1 \le T \le 10000$), som representerar antalet testfall.

För varje testfall består indatan av en enda rad med två heltal $n, p$ ($1 \le n \le 3000, 2 \le p \le 10^9 + 9$), som representerar antalet noder i det rotade trädet samt modulen som Lilla C tillhandahållit.

Det garanteras att den totala summan av $n$ för alla testfall inte överstiger $10000$.

Utdata

För varje testfall, skriv ut en enda rad med ett heltal som representerar svaret modulo $p$.

Exempel

Exempelindata 1

8
1 1000000009
5 1000000009
10 1000000009
15 1000000009
100 1000000009
150 1000000009
1000 1000000009
1500 1000000009

Exempelutdata 1

1
6
207
10904
478868953
202933416
152259136
264735211