Aby rozstrzygnąć, czy drzewa ukorzenione są izomorficzne (w tym zadaniu nie jest wymagana wcześniejsza wiedza o izomorfizmie drzew), często stosowanym algorytmem jest haszowanie drzew (tree hashing). Przy odpowiednio dobranej funkcji haszującej nieizomorficzne drzewa ukorzenione z dużym prawdopodobieństwem dają różne wartości hasza, choć kolizji haszy również trudno uniknąć.

Istnieją różne implementacje funkcji haszujących, jednak niektóre projekty takich funkcji nie są do końca poprawne. Mały C ma właśnie taką „nie do końca poprawną” funkcję haszującą, zdefiniowaną następująco: niech $sz_x$ oznacza liczbę wierzchołków zawartych w poddrzewie wierzchołka $x$, a $son_x$ niech będzie zbiorem wszystkich synów wierzchołka $x$. Dla drzewa ukorzenionego o korzeniu $r$ jego wartość hasza $h(r)$ definiujemy jako:

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

gdzie $f$ oznacza dowolne przekształcenie ze zbioru dodatnich liczb całkowitych w zbiór dodatnich liczb całkowitych, tj. $f \in \{\varphi : \mathbb{Z}^+ \to \mathbb{Z}^+\}$. W szczególności wartość hasza dla drzewa ukorzenionego złożonego z tylko jednego wierzchołka wynosi $1$.

Następnie Mały C definiuje, że jeśli dla dwóch drzew ukorzenionych przy żadnym wyborze funkcji $f$ nie da się otrzymać różnych wartości hasza, to drzewa te nazywamy nierozróżnialnymi; w przeciwnym razie, jeśli istnieje taki wybór funkcji $f$, dla którego oba drzewa dają różne wartości hasza, to drzewa te nazywamy rozróżnialnymi.

Mały C chce użyć tej funkcji haszującej do wygenerowania jak największej liczby ukorzenionych drzew binarnych, czyli takich drzew ukorzenionych, w których każdy wierzchołek ma co najwyżej dwóch synów. Mały C liczy na to, że obliczysz maksymalną liczbę parami rozróżnialnych ukorzenionych drzew binarnych zawierających $n$ wierzchołków. Oczywiście odpowiedź może być bardzo duża, dlatego Mały C przygotował dla Ciebie modulo $p$ — wynik należy podać modulo $p$.

Wejście

To zadanie zawiera wiele przypadków testowych. Pierwszy wiersz wejścia zawiera liczbę całkowitą $T$ ($1 \le T \le 10000$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego wejście składa się z pojedynczego wiersza zawierającego dwie liczby całkowite $n, p$ ($1 \le n \le 3000, 2 \le p \le 10^9 + 9$), oznaczające liczbę wierzchołków w drzewie ukorzenionym oraz modulo podane przez Małego C.

Gwarantowane jest, że łączna suma $n$ dla wszystkich przypadków testowych nie przekracza $10000$.

Wyjście

Dla każdego przypadku testowego wypisz pojedynczy wiersz z jedną liczbą całkowitą, oznaczającą wynik modulo $p$.

Przykład

Przykładowe wejście 1

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

Przykładowe wyjście 1

1
6
207
10904
478868953
202933416
152259136
264735211