Um festzustellen, ob gewurzelte Bäume isomorph sind (für dieses Problem benötigst du kein Vorwissen über Baumisomorphie), ist das Baum-Hashing (tree hashing) ein gängiger Algorithmus. Mit einer geeigneten Hashfunktion liefern nicht-isomorphe gewurzelte Bäume wahrscheinlich unterschiedliche Hashwerte, wenngleich Hashkollisionen ebenfalls schwer zu vermeiden sind.

Es gibt verschiedene Implementierungen von Hashfunktionen, aber manche Entwürfe von Hashfunktionen sind nicht ganz korrekt. Little C hat eine solche „nicht ganz korrekte“ Hashfunktion, die wie folgt definiert ist: Sei $sz_x$ die Anzahl der Knoten im Teilbaum von $x$ und $son_x$ die Menge aller Kindknoten von $x$. Für einen gewurzelten Baum mit Wurzel $r$ ist sein Hashwert $h(r)$ definiert als:

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

wobei $f$ eine beliebige Abbildung von der Menge der positiven ganzen Zahlen in die Menge der positiven ganzen Zahlen darstellt, d. h. $f \in \{\varphi : \mathbb{Z}^+ \to \mathbb{Z}^+\}$. Insbesondere beträgt der Hashwert für einen gewurzelten Baum mit nur einem Knoten $1$.

Als Nächstes definiert Little C für zwei gewurzelte Bäume: Wenn es für alle Wahlen von $f$ unmöglich ist, unterschiedliche Hashwerte zu berechnen, dann heißen die beiden Bäume nicht unterscheidbar; existiert hingegen eine Wahl von $f$, sodass für die beiden Bäume unterschiedliche Hashwerte berechnet werden können, dann heißen die beiden Bäume unterscheidbar.

Little C möchte mithilfe dieser Hashfunktion so viele gewurzelte Binärbäume wie möglich erzeugen – das sind gewurzelte Bäume, in denen jeder Knoten höchstens zwei Kindknoten hat. Little C hofft, dass du die maximale Anzahl paarweise unterscheidbarer gewurzelter Binärbäume mit $n$ Knoten berechnen kannst. Natürlich kann die Antwort sehr groß sein, weshalb Little C einen Modul $p$ für dich vorbereitet hat, sodass du dein Ergebnis modulo $p$ berechnen musst.

Eingabe

Dieses Problem enthält mehrere Testfälle. Die erste Zeile der Eingabe enthält eine ganze Zahl $T$ ($1 \le T \le 10000$), die die Anzahl der Testfälle angibt.

Für jeden Testfall besteht die Eingabe aus einer einzelnen Zeile mit zwei ganzen Zahlen $n, p$ ($1 \le n \le 3000, 2 \le p \le 10^9 + 9$), die die Anzahl der Knoten im gewurzelten Baum und den von Little C vorgegebenen Modul darstellen.

Es ist garantiert, dass die Gesamtsumme von $n$ für alle Testfälle $10000$ nicht überschreitet.

Ausgabe

Gib für jeden Testfall eine einzelne Zeile mit einer ganzen Zahl aus, die das Ergebnis der Antwort modulo $p$ darstellt.

Beispiel

Beispieleingabe 1

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

Beispielausgabe 1

1
6
207
10904
478868953
202933416
152259136
264735211