• 时间：1s
• 空间：256M

题目描述

小 Z 是算法竞赛社团的指导老师，他指导了 $N$ 个队员，编号为 $1,2,\cdots,N$，编号为 $i$ 的队员能力值为 $a_i$ 。

现在小 Z 要选一些队伍去参加比赛，每个队伍由若干个编号连续的队员组成，也就是说一个队伍可以被描述成一个区间$[l,r]$ ，由编号为$l,l+ 1,\cdots,r$ 的队员组成。每位队员最多被选入一支队伍中。

选拔方案可以用一个区间的序列$[l_1,r_1],[l_2,r_2],\cdots,[l_k,r_k]$ 来描述，代表着该方案选拔了$k$ 只队伍，第$i$ 只队伍由编号在$[l_i,r_i]$ 的队员组成。形式化地，要求：

• $1\le k\le N$
• $\forall i\in \{1,2,\cdots,k\},~1\le l_i\le r_i\le N$
• $\forall i\in \{1,2,\cdots,k-1\},~r_i<l_{i+1}$

我们称两个选拔方案不同，当且仅当两个方案对应的区间的序列不同。

根据过去的经验，一个队伍的综合能力值为这个队伍中所有队员能力值的最大公约数 (gcd)。小 Z 希望他选出的所有队伍综合能力值相同，因此他定义一个选拔方案是好的，当且仅当

$$\mathop{\text{gcd}}\limits_{i\in [l_1,r_1]}\{a_i\} = \mathop{\text{gcd}}\limits_{i\in [l_2,r_2]}\{ a_i\} = \cdots = \mathop{\text{gcd}}\limits_{i\in [l_k,r_k]}\{a_i\} $$

现在小 Z 想知道，对于每名选手，有多少个好的选拔方案，会将其选入在某一队伍中。

输入格式

从 selection.in 文件读入数据。

第一行一个整数 $N$，表示选手数。

第二行 $N$ 个整数，$a_1,a_2,\dots,a_N$，表示每位选手的能力值。

输出格式

输出到 selection.out 文件。

输出一行 $N$ 个整数，第 $i$ 个数表示有几个好的选拔方案使得第 $i$ 名选手在某一队中。由于答案很大，输出的数字对 $998244353$ 取模。

样例

5
2 6 4 1 2

10 13 13 8 10

样例 2

点击链接 ex_selection2.in 和 ex_selection2.out 下载大样例 2 的输入数据和输出数据。

数据范围

对于所有数据， $1 \leq N\leq 10^5$， 对于所有 $1 \leq i \leq N$，$1 \leq a_i \leq 10^9$。

子任务	得分	附加约束条件
$1$	$8$	$N\le 10, a_i\le 100$
$2$		所有 $a_i$ 均等于 $1$
$3$	$16$	$N\le 100$
$4$		$N\le 1000$
$5$		对所有 $a_i$ 均存在某个整数 $w_i$ ，使得 $a_i = 2^{w_i}$
$6$	$36$	无附加限制