Para determinar si dos árboles con raíz son isomorfos (en este problema no necesitas conocimientos previos sobre isomorfismo de árboles), un algoritmo común consiste en utilizar hashing de árboles. Con una función hash adecuada, es probable que los árboles con raíz no isomorfos produzcan valores hash diferentes, aunque las colisiones hash también son difíciles de evitar.

Existen diversas implementaciones de funciones hash, pero algunos diseños de funciones hash no son del todo correctos. Little C tiene una de esas funciones hash «no muy correctas», definida como sigue: sea $sz_x$ el número de vértices contenidos en el subárbol de $x$, y sea $son_x$ el conjunto de todos los nodos hijos de $x$. Para un árbol con raíz en $r$, su valor hash $h(r)$ se define como:

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

donde $f$ representa cualquier aplicación del conjunto de los enteros positivos en el conjunto de los enteros positivos, es decir, $f \in \{\varphi : \mathbb{Z}^+ \to \mathbb{Z}^+\}$. En particular, el valor hash de un árbol con raíz que tiene un solo nodo es $1$.

A continuación, Little C define que, para dos árboles con raíz, si para todas las elecciones de $f$ es imposible calcular valores hash diferentes, entonces se dice que los dos árboles son indistinguibles; en caso contrario, si existe una elección de $f$ tal que los dos árboles puedan producir valores hash diferentes, entonces se dice que los dos árboles son distinguibles.

Little C quiere usar esta función hash para generar tantos árboles binarios con raíz como sea posible, que son árboles con raíz en los que cada nodo tiene como máximo dos nodos hijos. Little C espera que puedas calcular el número máximo de árboles binarios con raíz distinguibles entre sí que contienen $n$ nodos. Por supuesto, la respuesta puede ser muy grande, por lo que Little C ha preparado un módulo $p$ para ti, y debes dar tu resultado módulo $p$.

Entrada

Este problema contiene múltiples casos de prueba. La primera línea de la entrada contiene un entero $T$ ($1 \le T \le 10000$), que representa el número de casos de prueba.

Para cada caso de prueba, la entrada consta de una sola línea con dos enteros $n, p$ ($1 \le n \le 3000, 2 \le p \le 10^9 + 9$), que representan el número de nodos en el árbol con raíz y el módulo proporcionado por Little C.

Se garantiza que la suma total de $n$ para todos los casos de prueba no supera $10000$.

Salida

Para cada caso de prueba, imprime una sola línea con un entero, que representa el resultado de la respuesta módulo $p$.

Ejemplo

Entrada de ejemplo 1

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

Salida de ejemplo 1

1
6
207
10904
478868953
202933416
152259136
264735211