Để xác định xem các cây có gốc có đẳng cấu với nhau hay không (trong bài toán này, bạn không cần kiến thức nền tảng về đẳng cấu cây), một thuật toán phổ biến là sử dụng băm cây (tree hashing). Với một hàm băm phù hợp, các cây có gốc không đẳng cấu nhiều khả năng sẽ cho ra các giá trị băm khác nhau, nhưng va chạm băm cũng rất khó tránh khỏi.

Có nhiều cách cài đặt hàm băm khác nhau, nhưng một số thiết kế hàm băm lại không thực sự đúng đắn. Little C có một hàm băm "không thực sự đúng đắn" như vậy, được định nghĩa như sau: Gọi $sz_x$ là số lượng đỉnh nằm trong cây con gốc $x$, và $son_x$ là tập hợp tất cả các đỉnh con trực tiếp của $x$. Đối với một cây có gốc với $r$ là gốc, giá trị băm $h(r)$ của nó được định nghĩa là:

$$h(r) = 1 + \sum_{v \in son_r} h(v) \times f(sz_v)$$

trong đó $f$ biểu thị một ánh xạ bất kỳ từ tập hợp các số nguyên dương vào tập hợp các số nguyên dương, tức là $f \in \{\varphi : \mathbb{Z}^+ \to \mathbb{Z}^+\}$. Đặc biệt, giá trị băm của một cây có gốc chỉ gồm một đỉnh là $1$.

Tiếp theo, Little C định nghĩa rằng đối với hai cây có gốc, nếu với mọi cách chọn $f$ đều không thể tính ra hai giá trị băm khác nhau, thì hai cây đó được gọi là không thể phân biệt; ngược lại, nếu tồn tại một cách chọn $f$ sao cho hai cây tính ra được hai giá trị băm khác nhau, thì hai cây đó được gọi là có thể phân biệt.

Little C muốn sử dụng hàm băm này để sinh ra nhiều cây nhị phân có gốc nhất có thể (đó là những cây có gốc mà mỗi đỉnh có tối đa hai đỉnh con). Little C hy vọng bạn có thể tính được số lượng tối đa các cây nhị phân có gốc gồm $n$ đỉnh đôi một có thể phân biệt được. Tất nhiên, đáp án có thể rất lớn, vì vậy Little C đã chuẩn bị sẵn một số modulo $p$ cho bạn, và bạn cần lấy kết quả theo modulo $p$.

Dữ liệu vào

Bài toán này gồm nhiều bộ dữ liệu. Dòng đầu tiên của dữ liệu vào chứa một số nguyên $T$ ($1 \le T \le 10000$), biểu thị số lượng bộ dữ liệu.

Đối với mỗi bộ dữ liệu, dữ liệu vào gồm một dòng duy nhất chứa hai số nguyên $n, p$ ($1 \le n \le 3000, 2 \le p \le 10^9 + 9$), lần lượt biểu thị số lượng đỉnh trong cây có gốc và số modulo do Little C cung cấp.

Dữ liệu đảm bảo tổng của $n$ qua tất cả các bộ dữ liệu không vượt quá $10000$.

Dữ liệu ra

Đối với mỗi bộ dữ liệu, in ra một dòng duy nhất chứa một số nguyên biểu thị kết quả của đáp án theo modulo $p$.

Ví dụ

Dữ liệu vào mẫu 1

8
1 1000000009
5 1000000009
10 1000000009
15 1000000009
100 1000000009
150 1000000009
1000 1000000009
1500 1000000009

Dữ liệu ra mẫu 1

1
6
207
10904
478868953
202933416
152259136
264735211