Cool P #1

题目描述

Given a sequence of $n$ positive integers $a_1, a_2, \dots, a_n$.

For every prefix of length $k$ ($1 \le k \le n$), consider all subsets of indices $S \subseteq \{1, 2, \dots, k\}$. Let $P(S) = \prod_{i \in S} a_i$. Count the number of subsets $S$ for which $P(S)$ is a perfect square.

The empty subset is allowed; its product is defined as $P(\varnothing) = 1$, which is a perfect square.

Two subsets are considered different if their sets of indices differ.

Since the answer can be large, output each count modulo $998244353$.

输入格式

The first line contains a single integer $n$ ($1 \le n \le 5 \times 10^5$).

The second line contains $n$ space-separated integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$).

输出格式

Print exactly $n$ integers in a single line, separated by spaces. The $k$-th integer ($1 \le k \le n$) should be the answer for the prefix of length $k$, modulo $998244353$.

样例输入 #1

5
2 3 6 4 5

样例输出 #1

1
1
2
4
4

样例输入 #2

5
6 10 15 30 60

样例输出 #2

1
1
2
2
4