Sen selvittämiseksi, ovatko juurelliset puut isomorfisia (tässä tehtävässä et tarvitse ennakkotietoja puiden isomorfiasta), yleinen algoritmi on käyttää puuhajautusta (tree hashing). Sopivalla hajautusfunktiolla ei-isomorfiset juurelliset puut tuottavat todennäköisesti eri hajautusarvot, mutta törmäyksiä on silti vaikea välttää.

Hajautusfunktioista on erilaisia toteutuksia, mutta jotkin hajautusfunktioiden rakenteet eivät ole kovin oikeita. Pikku C:llä on tällainen ”ei kovin oikea” hajautusfunktio, joka määritellään seuraavasti: Olkoon $sz_x$ solmun $x$ alipuuhun kuuluvien solmujen lukumäärä ja $son_x$ solmun $x$ kaikkien lapsisolmujen joukko. Juurelliselle puulle, jonka juuri on $r$, sen hajautusarvo $h(r)$ määritellään kaavalla:

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

missä $f$ tarkoittaa mitä tahansa kuvausta positiivisten kokonaislukujen joukosta positiivisten kokonaislukujen joukkoon, eli $f \in \{\varphi : \mathbb{Z}^+ \to \mathbb{Z}^+\}$. Erityisesti vain yhdestä solmusta koostuvan juurellisen puun hajautusarvo on $1$.

Seuraavaksi Pikku C määrittelee, että jos kahdelle juurelliselle puulle on kaikilla kuvauksen $f$ valinnoilla mahdotonta saada eri hajautusarvoja, näitä kahta puuta sanotaan erottamattomiksi; muussa tapauksessa, jos on olemassa sellainen kuvauksen $f$ valinta, jolla puille saadaan eri hajautusarvot, näitä kahta puuta sanotaan erotettaviksi.

Pikku C haluaa käyttää tätä hajautusfunktiota luodakseen mahdollisimman monta juurellista binääripuuta, eli juurellista puuta, joissa jokaisella solmulla on enintään kaksi lapsisolmua. Pikku C toivoo sinun laskevan, kuinka monta $n$ solmua sisältävää keskenään erotettavaa juurellista binääripuuta voi enintään olla. Vastaus voi tietysti olla hyvin suuri, joten Pikku C on varannut sinulle jakajan $p$, ja sinun tulee ilmoittaa tulos modulo $p$.

Syöte

Tässä tehtävässä on useita testitapauksia. Syötteen ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 10000$), joka ilmoittaa testitapausten lukumäärän.

Jokaiselle testitapaukselle syöte koostuu yhdestä rivistä, jolla on kaksi kokonaislukua $n, p$ ($1 \le n \le 3000, 2 \le p \le 10^9 + 9$), jotka ilmoittavat juurellisen puun solmujen lukumäärän sekä Pikku C:n antaman jakajan.

On taattu, että lukujen $n$ kokonaissumma yli kaikkien testitapausten ei ylitä arvoa $10000$.

Tuloste

Tulosta jokaiselle testitapaukselle yksi rivi, jolla on kokonaisluku: vastauksen jakojäännös modulo $p$.

Esimerkki

Esimerkkisyöte 1

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

Esimerkkituloste 1

1
6
207
10904
478868953
202933416
152259136
264735211