F2. Speedbreaker Counting (Medium Version)
time limit per test
10 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
NightHawk22 - Isolation
⠀

This is the medium version of the problem. In the three versions, the constraints on $$$n$$$ and the time limit are different. You can make hacks only if all the versions of the problem are solved.

This is the statement of Problem D1B:

  • There are $$$n$$$ cities in a row, numbered $$$1, 2, \ldots, n$$$ left to right.
    • At time $$$1$$$, you conquer exactly one city, called the starting city.
    • At time $$$2, 3, \ldots, n$$$, you can choose a city adjacent to the ones conquered so far and conquer it.

    You win if, for each $$$i$$$, you conquer city $$$i$$$ at a time no later than $$$a_i$$$. A winning strategy may or may not exist, also depending on the starting city. How many starting cities allow you to win?

For each $$$0 \leq k \leq n$$$, count the number of arrays of positive integers $$$a_1, a_2, \ldots, a_n$$$ such that

  • $$$1 \leq a_i \leq n$$$ for each $$$1 \leq i \leq n$$$;
  • the answer to Problem D1B is $$$k$$$.

The answer can be very large, so you have to calculate it modulo a given prime $$$p$$$.

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 only line of each test case contains two integers $$$n$$$, $$$p$$$ ($$$1 \le n \le 500$$$, $$$10^8 \leq p \leq 10^9$$$, $$$p$$$ is prime) — the number of cities and the modulo.

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

Output

For each test case, output $$$n+1$$$ integers: the $$$i$$$-th integer should be the number of arrays that satisfy the conditions for $$$k = i-1$$$.

Example
Input
11
1 998244353
2 998244353
3 998244353
4 998244353
5 998244353
6 998244353
7 998244353
8 998244353
9 998244353
10 102275857
10 999662017
Output
0 1 
1 2 1 
14 7 4 2 
183 34 19 16 4 
2624 209 112 120 48 12 
42605 1546 793 992 468 216 36 
785910 13327 6556 9190 4672 2880 864 144 
16382863 130922 61939 94992 50100 36960 14256 4608 576 
382823936 1441729 657784 1086596 583344 488700 216000 96480 23040 2880 
20300780 17572114 7751377 13641280 7376068 6810552 3269700 1785600 576000 144000 14400 
944100756 17572114 7751377 13641280 7376068 6810552 3269700 1785600 576000 144000 14400
Note

In the first test case,

  • arrays with $$$1$$$ good starting city: $$$[1]$$$.

In the second test case,

  • arrays with $$$0$$$ good starting cities: $$$[1, 1]$$$;
  • arrays with $$$1$$$ good starting city: $$$[1, 2]$$$, $$$[2, 1]$$$;
  • arrays with $$$2$$$ good starting cities: $$$[2, 2]$$$.

In the third test case,

  • arrays with $$$0$$$ good starting cities: $$$[1, 1, 1]$$$, $$$[1, 1, 2]$$$, $$$[1, 1, 3]$$$, $$$[1, 2, 1]$$$, $$$[1, 2, 2]$$$, $$$[1, 3, 1]$$$, $$$[1, 3, 2]$$$, $$$[2, 1, 1]$$$, $$$[2, 1, 2]$$$, $$$[2, 2, 1]$$$, $$$[2, 2, 2]$$$, $$$[2, 3, 1]$$$, $$$[2, 3, 2]$$$, $$$[3, 1, 1]$$$;
  • arrays with $$$1$$$ good starting city: $$$[1, 2, 3]$$$, $$$[1, 3, 3]$$$, $$$[2, 1, 3]$$$, $$$[3, 1, 2]$$$, $$$[3, 1, 3]$$$, $$$[3, 2, 1]$$$, $$$[3, 3, 1]$$$;
  • arrays with $$$2$$$ good starting cities: $$$[2, 2, 3]$$$, $$$[2, 3, 3]$$$, $$$[3, 2, 2]$$$, $$$[3, 3, 2]$$$;
  • arrays with $$$3$$$ good starting cities: $$$[3, 2, 3]$$$, $$$[3, 3, 3]$$$.