题目描述

给定长度为 $n$ 的正整数数列 $a_1,a_2,…,a_n$ 。

定义不交区间集为若干不交的区间 $[l_1,r_1],[l_2,r_2],⋯,[l_k,r_k]$ 的集合，其中任意集合 $[l_i,r_i]$ 满足 $1≤l_i≤r_i≤n$。

我们称两个不交区间集不同，当且仅当这两个区间的集合不同。

我们称一个不交区间集是好的，当且仅当

$$\gcd\limits_{i∈[l_1,r_1]}\{a_i\}=\gcd\limits_{i∈[l_2,r_2]}\{a_i\}=⋯=\gcd\limits_{i∈[l_k,r_k]}\{a_i\} $$

请你对每个 $a_i$ 求出，有多少个好的不交区间集，会将其选入在某一个区间中。

输入格式

第一行一个整数 $n$ ($1≤n≤10^5$)，代表数列的长度。

第二行 $n$ 个整数，$a_1,a_2,…,a_n$ ($1≤a_i≤10^9$)。

输出格式

输出一行 $n$ 个整数，第 $i$ 个数表示有几个好的不交区间集，会将 $a_i$ 选入在某一个区间中。

由于答案很大，输出的数字对 $998244353$ 取模。

输入样例

6
3 6 12 2 4 1

输出样例

9 13 15 15 12 9