لتحديد ما إذا كانت الأشجار المجذرة متماثلة الشكل (في هذه المسألة، لا تحتاج إلى معرفة مسبقة بتماثل الأشجار)، تتمثل إحدى الخوارزميات الشائعة في استخدام تجزئة الشجرة (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