כדי לקבוע האם עצים מושרשים הם איזומורפיים (בבעיה זו אינכם זקוקים לידע מוקדם על איזומורפיזם של עצים), אלגוריתם נפוץ הוא שימוש בגיבוב עצים (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