题目描述

接下来有 \(n\) 天，你想安排 \(m\) 场演唱会，第 \(i\) 场会在区间 \([l_i, r_i]\) 的天里举行（\(1 \le l_i \le r_i \le n\)），这些区间满足两两没有包含关系。即对于任意两场不同的演唱会 \(i\) 和 \(j\)，不能同时满足 \(l_i \le l_j\) 且 \(r_j \le r_i\)。

作为管理，你希望将这些演唱会分配给尽可能少的乐队，要求不能存在某一天某一支乐队同时需要参加两场演唱会。也就是说，同一支乐队负责的各个演唱会区间在天数上互不相交。那么你至少得请多少支乐队？

这个问题对你来说太简单了，所以你想把问题变得更有挑战性：现在假设具体的 \(m, l_i, r_i\) 都是未知的，你只想在所有可以安排的合法的非空时间段集合 \(\{[l_i, r_i]\}\) 中，探究所需的乐队数目的情况。

具体来说，对每个 \(k = 1\sim n\)，求出有多少个不包含相同元素、且两两没有包含关系的非空时间段集合（题目包含空集方案，即不选任何演唱会），满足能够全部分配给 \(k\) 支乐队内。也就是说所需乐队数 \(\le k\)。

由于答案可能非常大，请将数量对 \(998244353\) 取模后输出。

输入格式

本题开启多组测试数据。第一行包含一个整数 \(T\)，表示测试用例的数量。（\(1 \le T \le 5\)）

接下来的 \(T\) 行，每行包含一个整数 \(n\) （\(1 \le n \le 500\)），代表问题中给定的天数。

保证 \(\sum n \le 2000\)。

输出格式

对于每个测试用例，输出包含 \(n\) 个整数的一行，相邻两个整数之间用一个空格分隔。

第 \(k\) 个整数表示：在全部合法的时间段集合中，所需乐队数不超过 \(k\) 支的集合数目，结果需对 \(998244353\) 取模。

样例输入

4
3
5
9
15

样例输出

13 14 14
89 131 132 132 132
4181 14041 16645 16795 16796 16796 16796 16796 16796
1346269 16420730 30664890 34818270 35331134 35357237 35357669 35357670 35357670 35357670 35357670 35357670 35357670 35357670 35357670