AT_ndpc2026_l.LCM

You are given a positive integer $N$ and a permutation $A = (A_1, A_2, \dots, A_N)$ of $(1, 2, \dots, N)$.

Consider a directed graph $G$ with $N$ vertices numbered from $1$ to $N$. For every pair of integers $(i, j)$ such that $1 \leq i < j \leq N$, there are $\mathrm{LCM}(A_i, A_j)$ directed edges from vertex $i$ to vertex $j$. (Here, $\mathrm{LCM}$ denotes the least common multiple.) There are no other edges in $G$.

For each $v = 2, 3, \dots, N$, find the number of paths from vertex $1$ to vertex $v$, modulo $998244353$. Here, two paths are considered different if the sets of edges they pass through are different.

给定一个正整数 $N$ 和 $(1, 2, \dots, N)$ 的一个排列 $A = (A_1, A_2, \dots, A_N)$。

考虑一个包含 $N$ 个顶点（编号为 $1$ 到 $N$）的有向图 $G$。对每一对满足 $1 \leq i < j \leq N$ 的整数 $(i, j)$，从顶点 $i$ 到顶点 $j$ 恰好有 $\mathrm{LCM}(A_i, A_j)$ 条有向边。（此处 $\mathrm{LCM}$ 表示最小公倍数。）图 $G$ 中不存在其他边。

对每个 $v = 2, 3, \dots, N$，求从顶点 $1$ 到顶点 $v$ 的路径条数，结果对 $998244353$ 取模。注意：若两条路径经过的边集不同，则视为不同的路径。

The input is given from standard input in the following format:

$N$
$A_1$ $A_2$ $\dots$ $A_N$

输入从标准输入中按以下格式给出：

$N$
$A_1$ $A_2$ $\dots$ $A_N$

Print $N-1$ lines. On the $i$-th line, output the answer for $v = i+1$.

输出 $N-1$ 行。在第 $i$ 行中，输出 $v = i+1$ 时的答案。

Sample 1 Explanation:
The directed edges in $G$ are as follows:

• From vertex $1$ to vertex $2$: $6$ edges
• From vertex $1$ to vertex $3$: $3$ edges
• From vertex $1$ to vertex $4$: $12$ edges
• From vertex $2$ to vertex $3$: $2$ edges
• From vertex $2$ to vertex $4$: $4$ edges
• From vertex $3$ to vertex $4$: $4$ edges

Constraints

• $2 \leq N \leq 2 \times 10^5$
• $(A_1, A_2, \dots, A_N)$ is a permutation of $(1, 2, \dots, N)$
• All input values are integers

样例 1 解释：
图 $G$ 中的有向边如下所示：

• 从顶点 $1$ 到顶点 $2$：$6$ 条边
• 从顶点 $1$ 到顶点 $3$：$3$ 条边
• 从顶点 $1$ 到顶点 $4$：$12$ 条边
• 从顶点 $2$ 到顶点 $3$：$2$ 条边
• 从顶点 $2$ 到顶点 $4$：$4$ 条边
• 从顶点 $3$ 到顶点 $4$：$4$ 条边

约束条件

• $2 \leq N \leq 2 \times 10^5$
• $(A_1, A_2, \dots, A_N)$ 是 $(1, 2, \dots, N)$ 的一个排列
• 所有输入值均为整数