F2. 破速者计数（中等版）

每个测试的时间限制： $10$ 秒
内存限制： $1024$ MB

NightHawk22 - Isolation

---

题目描述

这是该问题的中等版本。三个版本的 $n$ 约束和时间限制不同。
只有解决了该问题的所有版本，你才能进行 Hack。

本题是 Problem D1B 的陈述：

有 $n$ 个城市排成一行，从左到右编号为 $1, 2, \dots, n$。
在时间 $1$，你恰好征服一个城市，称为起始城市。
在时间 $2, 3, \dots, n$，你可以选择一个与已征服城市相邻的城市并将其征服。
你获胜的条件是：对于每个 $i$，你在时间 $\le a_i$ 时征服了城市 $i$。
获胜策略可能存在，也可能不存在，并且取决于起始城市。
问：有多少个起始城市能够让你获胜？

对于每个 $0 \le k \le n$，统计满足以下条件的正整数数组 $a_1, a_2, \dots, a_n$ 的个数：

• 对于每个 $1 \le i \le n$，有 $1 \le a_i \le n$；
• Problem D1B 的答案（即能获胜的起始城市数量）恰好等于 $k$。

答案可能非常大，你需要对给定的素数 $p$ 取模后输出。

---

输入格式

每个测试包含多个测试用例。
第一行包含一个整数 $t$（$1 \le t \le 500$），表示测试用例的数量。
接下来每个测试用例一行，包含两个整数 $n$ 和 $p$（$1 \le n \le 500$，$10^8 \le p \le 10^9$，$p$ 是素数），分别表示城市数量和模数。

保证所有测试用例的 $n$ 之和不超过 $500$。

---

输出格式

对于每个测试用例，输出 $n+1$ 个整数：第 $i$ 个整数表示 $k = i-1$ 时满足条件的数组个数。

---

样例

输入：

11
1 998244353
2 998244353
3 998244353
4 998244353
5 998244353
6 998244353
7 998244353
8 998244353
9 998244353
10 102275857
10 999662017

输出：

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 

---

注释

在第一个测试用例中：

• 有 $1$ 个好的起始城市的数组：$[1]$。

在第二个测试用例中：

• 有 $0$ 个好的起始城市的数组：$[1,1]$；
• 有 $1$ 个好的起始城市的数组：$[1,2], [2,1]$；
• 有 $2$ 个好的起始城市的数组：$[2,2]$。

在第三个测试用例中：

• 有 $0$ 个好的起始城市的数组：$[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]$；
• 有 $1$ 个好的起始城市的数组：$[1,2,3], [1,3,3], [2,1,3], [3,1,2], [3,1,3], [3,2,1], [3,3,1]$；
• 有 $2$ 个好的起始城市的数组：$[2,2,3], [2,3,3], [3,2,2], [3,3,2]$；
• 有 $3$ 个好的起始城市的数组：$[3,2,3], [3,3,3]$。