题目描述

给定 $n$ 个点，编号 $1$ 至 $n$，任意两点 $x, y$ 之间均有且仅有一条边。如果 $x \cdot y$ 为完全平方数（也即存在整数 $z$ 满足 $z^2 = x \cdot y$），那么其边权为 $1$，否则为 $0$。

小蓝想要得到一棵生成树，其除 $1$ 以外的每个点都有一个编号小于自己的点与其相邻。求小蓝想得到的所有生成树中，边权和为 $0$ 至 $n-1$ 的分别各有多少种，请输出答案对 $998244353$ 取模的结果。

输入格式

输入一行包含一个整数 $n$。

输出格式

输出 $n$ 行，每行包含一个整数，依次表示边权和为 $0 \sim n-1$ 的生成树种数。

4

4
2
0
0

提示

评测用例规模与约定

• 对于 $60\%$ 的评测用例，$n \leq 5000$；
• 对于 $85\%$ 的评测用例，$n \leq 10^5$；

对于所有评测用例，$1 \leq n \leq 3 \times 10^5$。