루트 있는 트리들이 서로 동형인지 판별하기 위해(이 문제에서는 트리 동형에 대한 사전 지식이 필요하지 않습니다), 흔히 사용되는 알고리즘 중 하나는 트리 해싱(tree hashing)입니다. 적절한 해시 함수를 사용하면 동형이 아닌 루트 있는 트리들은 서로 다른 해시 값을 가질 가능성이 높지만, 해시 충돌을 피하는 것 또한 어렵습니다.

해시 함수에는 다양한 구현 방식이 있지만, 어떤 해시 함수 설계는 그리 올바르지 않습니다. Little 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$입니다.

다음으로 Little C는 두 루트 있는 트리에 대해, 가능한 모든 $f$의 선택에 대해서도 서로 다른 해시 값을 계산해 내는 것이 불가능하다면 두 트리를 구별 불가능(indistinguishable)하다고 정의합니다. 반대로 두 트리가 서로 다른 해시 값을 계산해 낼 수 있게 하는 $f$의 선택이 존재한다면 두 트리를 구별 가능(distinguishable)하다고 정의합니다.

Little C는 이 해시 함수를 사용하여 가능한 한 많은 루트 있는 이진 트리(각 정점이 최대 두 개의 자식 정점을 가지는 루트 있는 트리)를 생성하고자 합니다. Little C는 $n$개의 정점을 포함하며 서로 구별 가능한 루트 있는 이진 트리의 최대 개수를 여러분이 계산해 주기를 바랍니다. 물론 답이 매우 클 수 있으므로 Little C는 여러분을 위해 모듈로 $p$를 준비했으며, 결과를 $p$로 나눈 나머지를 구해야 합니다.

입력

이 문제는 여러 개의 테스트 케이스를 포함합니다. 입력의 첫 번째 줄에는 테스트 케이스의 수를 나타내는 정수 $T$ ($1 \le T \le 10000$)가 주어집니다.

각 테스트 케이스에 대해, 입력은 두 정수 $n, p$ ($1 \le n \le 3000, 2 \le p \le 10^9 + 9$)가 적힌 한 줄로 이루어지며, 각각 루트 있는 트리의 정점 수와 Little 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