Чтобы определить, являются ли корневые деревья изоморфными (в этой задаче предварительных знаний об изоморфизме деревьев не требуется), часто используют алгоритм хеширования деревьев. При подходящей хеш-функции неизоморфные корневые деревья с высокой вероятностью дают разные значения хеша, хотя коллизий хешей тоже трудно избежать.

Существуют различные реализации хеш-функций, но некоторые конструкции хеш-функций не совсем корректны. У Маленького 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