You are given an integer $n$ and an array $a$ of length $n-1$ whose elements are either $0$ or $1$.

Let us define the value of a permutation$^\dagger$ $p$ of length $m-1$ ($m \leq n$) by the following process.

Let $G$ be a graph of $m$ vertices labeled from $1$ to $m$ that does not contain any edges. For each $i$ from $1$ to $m-1$, perform the following operations:

• define $u$ and $v$ as the (unique) vertices in the weakly connected components$^\ddagger$ containing vertices $p_i$ and $p_i+1$ respectively with only incoming edges$^{\dagger\dagger}$;
• in graph $G$, add a directed edge from vertex $v$ to $u$ if $a_{p_i}=0$, otherwise add a directed edge from vertex $u$ to $v$ (if $a_{p_i}=1$).

Note that after each step, it can be proven that each weakly connected component of $G$ has a unique vertex with only incoming edges.

Then, the value of $p$ is the number of incoming edges of vertex $1$ of $G$.

For each $k$ from $1$ to $n-1$, find the sum of values of all $k!$ permutations of length $k$. Since this value can be big, you are only required to compute this value under modulo $998\,244\,353$.

Operations when $n=3$, $a=[0,1]$ and $p=[1,2]$

$^\dagger$ A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

$^\ddagger$ The weakly connected components of a directed graph is the same as the components of the undirected version of the graph. Formally, for directed graph $G$, define a graph $H$ where for all edges $a \to b$ in $G$, you add an undirected edge $a \leftrightarrow b$ in $H$. Then the weakly connected components of $G$ are the components of $H$.

$^{\dagger\dagger}$ Note that a vertex that has no edges is considered to have only incoming edges.

Input

The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $n$ ($2\le n\le 5 \cdot 10^5$).

The second line of each test case contains $n-1$ integers $a_1, a_2, \ldots, a_{n-1}$ ($a_i$ is $0$ or $1$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \cdot 10^5$.

Output

For each test case, output $n-1$ integers in a line, the $i$-th integer should represent the answer when $k=i$, under modulo $998\,244\,353$.

Note

Consider the first test case.

When $k=1$, there is only $1$ permutation $p$.

• When $p=[1]$, we will add a single edge from vertex $2$ to $1$. Vertex $1$ will have $1$ incoming edge. So the value of $[1]$ is $1$.

Therefore when $k=1$, the answer is $1$.

When $k=2$, there are $2$ permutations $p$.

• When $p=[1,2]$, we will add an edge from vertex $2$ to $1$ and an edge from $3$ to $1$. Vertex $1$ will have $2$ incoming edges. So the value of $[1,2]$ is $2$.
• When $p=[2,1]$, we will add an edge from vertex $3$ to $2$ and an edge from $2$ to $1$. Vertex $1$ will have $1$ incoming edge. So the value of $[2,1]$ is $1$.

Therefore when $k=2$, the answer is $2+1=3$.