E. Paired Bracket Sequences
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Farmer John is interested in bracket sequences with common pairings.

A balanced bracket sequence is one in which every opening bracket is matched with a later closing bracket, and no prefix contains more closing brackets than opening brackets.

For a balanced bracket sequence $$$s$$$, a pairing is a pair of positions $$$(i,j)$$$ with $$$i \lt j$$$ such that $$$s_i$$$ is an opening bracket, $$$s_j$$$ is a closing bracket, and the substring strictly between them is balanced.

Consider an ordered pair $$$(s,t)$$$ of balanced bracket sequences, where both $$$s$$$ and $$$t$$$ have length $$$2n$$$. A pairing $$$(i,j)$$$ is common to $$$s$$$ and $$$t$$$ if $$$(i,j)$$$ is a pairing in both sequences. For example, the bracket sequences $$$\texttt{(()())}$$$ and $$$\texttt{((()))}$$$ have one common pairing, namely the outer pair $$$(1,6)$$$.

Two ordered pairs $$$(s,t)$$$ and $$$(s',t')$$$ are considered different if $$$s \ne s'$$$ or $$$t \ne t'$$$.

For each $$$0 \le k \le n$$$, Farmer John wants to know the number of ordered pairs $$$(s,t)$$$ of balanced bracket sequences of length $$$2n$$$ with exactly $$$k$$$ common pairings. Since these numbers may be large, output them modulo $$$M$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 500$$$). The description of the test cases follows.

The first line of each testcase will contain two integers, $$$n$$$ and $$$M$$$ ($$$1 \leq n \leq 500$$$, $$$10^8 \leq M \leq 10^9$$$) — half the length of the bracket sequence and the modulo to output the answer in. It is guaranteed that $$$M$$$ is prime.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$500$$$.

Output

For each testcase, output $$$n + 1$$$ integers, the answer modulo $$$M$$$ for each $$$0 \leq k \leq n$$$.

Example
Input
5
1 998244353
2 998244353
3 998244353
4 998244353
8 998244353
Output
0 1 
2 0 2 
8 12 0 5 
62 64 56 0 14 
378790 646560 542960 296800 127400 34944 16016 0 1430
Note

For the first test case, there is only one balanced bracket sequence with $$$n=1$$$: $$$\texttt{()}$$$. It has exactly one pairing, namely $$$(1,2)$$$. Therefore, the only ordered pair of bracket sequences has exactly one common pairing, so the answer is $$$[0,1]$$$.

For the second test case, there are exactly two balanced bracket sequences with $$$n=2$$$: $$$a=\texttt{(())}$$$ and $$$b=\texttt{()()}$$$. The pairings of $$$a$$$ are $$$(1,4)$$$ and $$$(2,3)$$$, while the pairings of $$$b$$$ are $$$(1,2)$$$ and $$$(3,4)$$$.

Thus, the ordered pairs $$$(a,b)$$$ and $$$(b,a)$$$ have $$$0$$$ common pairings, while the ordered pairs $$$(a,a)$$$ and $$$(b,b)$$$ have $$$2$$$ common pairings. Therefore, the answer is $$$[2,0,2]$$$.