Stack 有一个长度为 $$$n$$$ 的数组 $$$a$$$,对于所有 $$$i$$$,$$$a_i = i$$$ ($$$1 \leq i \leq n$$$)。他将选择一个正整数 $$$k$$$ ($$$1 \leq k \leq \lfloor \frac{n-1}{2} \rfloor$$$) 并对 $$$a$$$ 任意次数(可能是 $$$0$$$)执行以下操作。
- 从 $$$a$$$ 中选择长度为 $$$2 \cdot k + 1$$$ 的子序列$$$^\dagger$$$ $$$s$$$。现在,他将从 $$$a$$$ 中删除 $$$s$$$ 的前 $$$k$$$ 个元素。为了保持完美平衡(所有事情都应该如此),他还将从 $$$a$$$ 中删除 $$$s$$$ 的最后 $$$k$$$ 元素。
Stack 想知道对于每个 $$$k$$$ ($$$1 \leq k \leq \lfloor \frac{n-1}{2} \rfloor$$$),他最终能得到多少个数组 $$$a$$$。由于 Stack 不擅长计算问题,因此他需要你的帮助。
由于数组数量可能太大,请以 $$$998\,244\,353$$$ 为模打印。
$$$^\dagger$$$ 序列 $$$x$$$ 是序列 $$$y$$$ 的子序列,如果 $$$x$$$ 可以通过删除多个(可能是零个或全部)元素从 $$$y$$$ 获得。例如,$$$[1, 3]$$$、$$$[1, 2, 3]$$$ 和 $$$[2, 3]$$$ 是 $$$[1, 2, 3]$$$ 的子序列。另一方面,$$$[3, 1]$$$ 和 $$$[2, 1, 3]$$$ 不是 $$$[1, 2, 3]$$$ 的子序列。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^3$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \leq n \leq 10^6$$$) — 数组 $$$a$$$ 的长度。
保证所有测试用例的$$$n$$$总和不超过$$$10^6$$$。
输出
对于每个测试,在新行上打印 $$$\lfloor \frac{n-1}{2} \rfloor$$$ 空格分隔的整数 - 第 $$$i$$$ 整数表示以 $$$998\,244\,353$$$ 为模的数组数量,如果 Stack 选择 $$$k=i$$$,则 Stack 可以获得该数。
示例
输入 #1
4 3 4 5 10
输出 #1
2 4 10 2 487 162 85 10
注意
在第一个测试用例中,$$$a$$$ 可能有两个 $$$k=1$$$:
- $$$[1,2,3]$$$;
- $$$[2]$$$.
在第二个测试用例中,$$$k=1$$$ 可能有四个 $$$a$$$:
- $$$[1,2,3,4]$$$;
- $$$[1,3]$$$;
- $$$[2,3]$$$;
- $$$[2,4]$$$.
在第三个测试用例中,对于 $$$k=2$$$ 来说,两个 $$$a$$$ 是可能的:
- $$$[1,2,3,4,5]$$$;
- $$$[3]$$$.