Түбірлі ағаштардың изоморфты екенін анықтау үшін (бұл есепте ағаштар изоморфизмі туралы алдын ала білім қажет емес) жиі қолданылатын алгоритм — ағаштарды хештеу (tree hashing). Лайықты хеш-функция таңдалса, изоморфты емес түбірлі ағаштар әртүрлі хеш мәндерін беруі әбден мүмкін, бірақ хеш коллизияларынан да қашып құтылу қиын.

Хеш-функцияларды іске асырудың түрлі жолдары бар, бірақ кейбір хеш-функциялардың құрылымы аса дұрыс емес. Кішкентай C-де келесідей анықталатын осындай «аса дұрыс емес» хеш-функция бар: $sz_x$ арқылы $x$ төбесінің ішкі ағашындағы төбелер санын, ал $son_x$ арқылы $x$ төбесінің барлық бала төбелерінің жиынын белгілейік. Түбірі $r$ болатын түбірлі ағаш үшін оның $h(r)$ хеш мәні былайша анықталады:

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

мұндағы $f$ — оң бүтін сандар жиынынан оң бүтін сандар жиынына кез келген бейнелеу, яғни $f \in \{\varphi : \mathbb{Z}^+ \to \mathbb{Z}^+\}$. Дербес жағдайда, тек бір ғана төбесі бар түбірлі ағаштың хеш мәні $1$-ге тең.

Әрі қарай, Кішкентай C екі түбірлі ағаш үшін $f$-тің барлық таңдауларында әртүрлі хеш мәндерін есептеп шығару мүмкін болмаса, бұл екі ағаш ажыратылмайтын деп аталады деп анықтайды; кері жағдайда, егер екі ағаш әртүрлі хеш мәндерін беретіндей $f$ таңдауы табылса, онда бұл екі ағаш ажыратылатын деп аталады.

Кішкентай C осы хеш-функцияны пайдаланып мүмкіндігінше көп түбірлі екілік ағаштарды (яғни әрбір төбесінде ең көп дегенде екі бала төбесі болатын түбірлі ағаштарды) құрастырғысы келеді. Кішкентай C сізден $n$ төбесі бар, өзара ажыратылатын түбірлі екілік ағаштардың ең көп санын есептеп беруіңізді үміт етеді. Әрине, жауап өте үлкен болуы мүмкін, сондықтан Кішкентай C сізге $p$ модулін дайындап қойды — нәтижені $p$ модулі бойынша шығаруыңыз керек.

Кіріс

Бұл есеп бірнеше тест жағдайларынан тұрады. Кірістің бірінші жолында тест жағдайларының санын білдіретін $T$ ($1 \le T \le 10000$) бүтін саны берілген.

Әрбір тест жағдайы үшін кіріс екі бүтін саннан — $n, p$ ($1 \le n \le 3000, 2 \le p \le 10^9 + 9$) тұратын жалғыз жолдан құралады, олар түбірлі ағаштағы төбелер санын және Кішкентай C берген модульді білдіреді.

Барлық тест жағдайлары үшін $n$ мәндерінің жалпы қосындысы $10000$-нан аспайтынына кепілдік беріледі.

Шығыс

Әрбір тест жағдайы үшін жауаптың $p$ модулі бойынша нәтижесін білдіретін бүтін саны бар жалғыз жолды шығарыңыз.

Мысал

Мысал кіріс 1

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

Мысал шығыс 1

1
6
207
10904
478868953
202933416
152259136
264735211