For å avgjøre om rotede trær er isomorfe (i denne oppgaven trenger du ingen forkunnskaper om treisomorfi), er en vanlig algoritme å bruke trehashing (tree hashing). Med en passende hashfunksjon vil ikke-isomorfe rotede trær sannsynligvis gi ulike hashverdier, men hashkollisjoner er også vanskelige å unngå.

Det finnes ulike implementasjoner av hashfunksjoner, men noen design av hashfunksjoner er ikke helt riktige. Lille C har en slik «ikke helt riktig» hashfunksjon, definert som følger: La $sz_x$ være antallet noder i undertreet til $x$, og la $son_x$ være mengden av alle barnenoder til $x$. For et rotet tre med $r$ som rot defineres hashverdien $h(r)$ som:

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

der $f$ representerer en vilkårlig avbildning fra mengden av positive heltall til mengden av positive heltall, det vil si $f \in \{\varphi : \mathbb{Z}^+ \to \mathbb{Z}^+\}$. Spesielt er hashverdien for et rotet tre med bare én node lik $1$.

Videre definerer Lille C at for to rotede trær gjelder følgende: hvis det for alle valg av $f$ er umulig å beregne ulike hashverdier, sies de to trærne å være uskjelnelige; ellers, hvis det finnes et valg av $f$ slik at de to trærne kan gi ulike hashverdier, sies de to trærne å være skjelnelige.

Lille C ønsker å bruke denne hashfunksjonen til å generere så mange rotede binære trær som mulig, altså rotede trær der hver node har høyst to barnenoder. Lille C håper du kan beregne det maksimale antallet parvis skjelnelige rotede binære trær som inneholder $n$ noder. Svaret kan selvfølgelig bli svært stort, så Lille C har gjort klar en modulus $p$ til deg, og du må oppgi resultatet ditt modulo $p$.

Inndata

Denne oppgaven inneholder flere testtilfeller. Den første linjen i inndataene inneholder et heltall $T$ ($1 \le T \le 10000$), som representerer antallet testtilfeller.

For hvert testtilfelle består inndataene av én enkelt linje med to heltall $n, p$ ($1 \le n \le 3000, 2 \le p \le 10^9 + 9$), som representerer antallet noder i det rotede treet og modulusen oppgitt av Lille C.

Det er garantert at den totale summen av $n$ for alle testtilfeller ikke overstiger $10000$.

Utdata

For hvert testtilfelle skal du skrive ut én enkelt linje med et heltall som representerer svaret modulo $p$.

Eksempel

Eksempelinndata 1

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

Eksempelutdata 1

1
6
207
10904
478868953
202933416
152259136
264735211