Pour déterminer si des arbres enracinés sont isomorphes (dans ce problème, aucune connaissance préalable sur l'isomorphisme d'arbres n'est requise), un algorithme courant consiste à utiliser le hachage d'arbres (tree hashing). Avec une fonction de hachage appropriée, des arbres enracinés non isomorphes ont de fortes chances de produire des valeurs de hachage différentes, bien que les collisions de hachage soient difficiles à éviter.

Il existe diverses implémentations de fonctions de hachage, mais certaines conceptions ne sont pas tout à fait correctes. Little C possède une telle fonction de hachage « pas très correcte », définie comme suit : soit $sz_x$ le nombre de sommets contenus dans le sous-arbre de $x$, et $son_x$ l'ensemble de tous les nœuds enfants de $x$. Pour un arbre enraciné de racine $r$, sa valeur de hachage $h(r)$ est définie par :

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

où $f$ représente n'importe quelle application de l'ensemble des entiers strictement positifs dans lui-même, c'est-à-dire $f \in \{\varphi : \mathbb{Z}^+ \to \mathbb{Z}^+\}$. En particulier, la valeur de hachage d'un arbre enraciné ne comportant qu'un seul nœud est $1$.

Ensuite, Little C définit que pour deux arbres enracinés, s'il est impossible d'obtenir des valeurs de hachage différentes quel que soit le choix de $f$, alors les deux arbres sont dits indiscernables ; sinon, s'il existe un choix de $f$ permettant d'obtenir des valeurs de hachage différentes pour les deux arbres, alors ils sont dits discernables.

Little C souhaite utiliser cette fonction de hachage pour générer autant d'arbres binaires enracinés que possible (c'est-à-dire des arbres enracinés où chaque nœud possède au plus deux nœuds enfants). Little C espère que vous pourrez calculer le nombre maximal d'arbres binaires enracinés deux à deux discernables contenant $n$ nœuds. Bien entendu, la réponse pouvant être très grande, Little C vous a préparé un modulo $p$, et vous devez donner votre résultat modulo $p$.

Entrée

Ce problème contient plusieurs jeux de tests. La première ligne de l'entrée contient un entier $T$ ($1 \le T \le 10000$), représentant le nombre de jeux de tests.

Pour chaque jeu de tests, l'entrée consiste en une seule ligne contenant deux entiers $n, p$ ($1 \le n \le 3000, 2 \le p \le 10^9 + 9$), représentant le nombre de nœuds de l'arbre enraciné et le modulo fourni par Little C.

Il est garanti que la somme totale de $n$ sur l'ensemble des jeux de tests ne dépasse pas $10000$.

Sortie

Pour chaque jeu de tests, affichez une seule ligne contenant un entier, représentant le résultat de la réponse modulo $p$.

Exemple

Entrée d'exemple 1

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

Sortie d'exemple 1

1
6
207
10904
478868953
202933416
152259136
264735211