F2. Speedbreaker Counting (Medium Version)time limit per test10 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard outputNightHawk22 - 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$$$.InputEach 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$$$.OutputFor 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$$$.ExampleInput111 9982443532 9982443533 9982443534 9982443535 9982443536 9982443537 9982443538 9982443539 99824435310 10227585710 999662017Output0 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 NoteIn 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]$$$.