如果一个数字集合中存在一个整数 $p > 1$，使得 $p$ 能整除该集合中的所有数字，则称该集合为“兄弟集合”。Malnar 先生收到了一份包含 $1$ 到 $n$ 的排列 $P$ 作为礼物，由于这个排列太长了，他决定只保留其中的前几个数字。

由于 Malnar 先生非常喜欢兄弟集合，他想知道对于排列 $P$ 的每一个前缀，其中包含多少个非空的兄弟子集。众所周知，Malnar 先生有比数子集更重要的事情要做，所以他请求你来帮助他。由于这些数字可能非常大，他只需要你输出结果对 $998\,244\,353$ 取模后的值。

输入格式

第一行包含一个自然数 $n$ ($1 \le n \le 3 \cdot 10^5$)。

第二行包含 $n$ 个数字，其中第 $i$ 个数字为 $P_i$，即排列 $P$ 的第 $i$ 个数字。

输出格式

输出 $n$ 行。第 $i$ 行应输出长度为 $i$ 的前缀中兄弟子集的数量对 $998\,244\,353$ 取模后的结果。

样例

样例输入 1

5
2 3 1 4 5

样例输出 1

1
2
2
4
5

样例输入 2

6
1 5 6 2 3 4

样例输出 2

0
1
2
4
6
10