F3. 破城者计数（困难版）

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

NightHawk22 - Isolation

⠀

这是本题的困难版本。在三个版本中，$n$ 的限制和时间限制不同。只有当所有版本的题目都通过后，你才能进行 hack。

本题是 Problem D1B 的叙述：

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

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

• 对每个 $1 \le i \le n$，有 $1 \le a_i \le n$；
• 问题 D1B 的答案是 $k$。

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

输入
每个测试点包含多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 3000$）。接下来每个测试用例的描述如下。
每个测试用例只有一行，包含两个整数 $n, p$（$1 \le n \le 3000$，$10^8 \le p \le 10^9$，$p$ 是质数）。
保证所有测试用例的 $n$ 之和不超过 $3000$。

输出
对于每个测试用例，输出 $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]$。