Til að skera úr um hvort rótuð tré séu einsmóta (í þessu verkefni þarftu ekki forþekkingu á einsmótun trjáa) er algengt reiknirit að nota trjátætingu (tree hashing). Með hentugu tætifalli er líklegt að óeinsmóta rótuð tré gefi ólík tætigildi, en árekstra í tætingu er einnig erfitt að forðast.

Til eru ýmsar útfærslur á tætiföllum, en sumar hannanir tætifalla eru ekki alveg réttar. Litli C er með slíkt „ekki alveg rétt“ tætifall sem skilgreint er á eftirfarandi hátt: Látum $sz_x$ vera fjölda hnúta í hluttrénu út frá $x$ og $son_x$ vera mengi allra barnahnúta $x$. Fyrir rótað tré með $r$ sem rót er tætigildi þess $h(r)$ skilgreint sem:

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

þar sem $f$ táknar hvaða vörpun sem er úr mengi jákvæðra heiltalna yfir í mengi jákvæðra heiltalna, þ.e. $f \in \{\varphi : \mathbb{Z}^+ \to \mathbb{Z}^+\}$. Sér í lagi er tætigildi rótaðs trés með aðeins einum hnúti jafnt og $1$.

Næst skilgreinir Litli C að fyrir tvö rótuð tré, ef ómögulegt er fyrir öll val á $f$ að reikna út ólík tætigildi, þá eru trén tvö sögð ógreinanleg; annars, ef til er val á $f$ þannig að trén tvö geti gefið ólík tætigildi, þá eru trén tvö sögð greinanleg.

Litli C vill nota þetta tætifall til að búa til eins mörg rótuð tvíundartré og mögulegt er, en það eru rótuð tré þar sem hver hnútur hefur í mesta lagi tvo barnahnúta. Litli C vonar að þú getir reiknað hámarksfjölda greinanlegra rótaðra tvíundartrjáa sem innihalda $n$ hnúta. Auðvitað getur svarið verið mjög stórt, svo Litli C hefur útbúið deili $p$ handa þér og þú þarft að skila niðurstöðunni módúló $p$.

Inntak

Þetta verkefni inniheldur mörg prófunartilvik. Fyrsta lína inntaksins inniheldur heiltölu $T$ ($1 \le T \le 10000$), sem táknar fjölda prófunartilvika.

Fyrir hvert prófunartilvik samanstendur inntakið af einni línu með tveimur heiltölum $n, p$ ($1 \le n \le 3000, 2 \le p \le 10^9 + 9$), sem tákna fjölda hnúta í rótaða trénu og deilinn sem Litli C gefur.

Tryggt er að heildarsumma $n$ fyrir öll prófunartilvik fari ekki yfir $10000$.

Úttak

Fyrir hvert prófunartilvik skal prenta eina línu með heiltölu sem táknar niðurstöðu svarsins módúló $p$.

Dæmi

Sýnidæmi inntaks 1

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

Sýnidæmi úttaks 1

1
6
207
10904
478868953
202933416
152259136
264735211