AT_arc185_e.[ARC185E] Adjacent GCD

定义一个整数序列 $B=(B_1,B_2,\dots,B_k)$ 的分数为 $\sum_{i=1}^{k-1}\gcd(B_i,B_{i+1})$。

给出一个整数序列 $A=(A_1,A_2,\dots,A_N)$，求出以下问题在 $m=1,2,\dots,N$ 时的答案：

• 序列 $A=(A_1,A_2,\dots,A_m)$ 有 $2^m-1$ 个非空子序列。求出这些子序列的分数之和对 $998244353$ 取模后的值。如果两个子序列在原序列中的位置不同，即使它们的元素全部相同，我们也认为它们是不同的。

输入来自标准输入，格式如下：

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

输出 $N$ 行，第 $i$ 行表示当 $m=i$ 时的答案。

样例 1 解释

以 $m=3$ 为例。以下是 $(A_1,A_2,A_3)=(9,6,4)$ 的所有非空子序列和分数：

• $(9)$，分数为 $0$。
• $(6)$，分数为 $0$。
• $(4)$，分数为 $0$。
• $(9,6)$，分数为 $\gcd(9,6)=3$。
• $(9,4)$，分数为 $\gcd(9,4)=1$。
• $(6,4)$，分数为 $\gcd(6,4)=2$。
• $(9,6,4)$，分数为 $\gcd(9,6)+\gcd(6,4)=3+2=5$。

因此当 $m=3$ 时答案为 $0+0+0+3+1+2+5=11$。

• $1\le N\le 5\times 10^5$
• $1\le A_i\le 10^5$
• 输入的值全部为整数