Щоб визначити, чи є кореневі дерева ізоморфними (у цій задачі попередніх знань про ізоморфізм дерев не потрібно), часто використовують алгоритм хешування дерев. За належної хеш-функції неізоморфні кореневі дерева з високою ймовірністю дають різні значення хешу, хоча колізій хешів також важко уникнути.

Існують різні реалізації хеш-функцій, але деякі конструкції хеш-функцій не зовсім коректні. У Маленького 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