#208 Crush

Statement

Statement language

There are $N$ students in Seondeok High School. The students are numbered $1,2,\cdots,N$ without duplication.

Each student has a crush on exactly one other student, not themselves. The teacher knows this information only for some students; for the remaining students, the teacher does not know whom they have a crush on.

When all unknown information is completed, the teacher wants to know the number of possible completions such that exactly $K$ pairs of students like each other. A pair of students liking each other means that two distinct students $i,j$ satisfy that $i$ has a crush on $j$ and $j$ has a crush on $i$ .

For each test case, compute the answer for every $K=0,1,2,\cdots,N-1$ . Since the number of possible completions can be large, print each answer modulo $998\ 244\ 353$ .

Input

The input is given in the following format.

$T$ $N$ $B_1\ B_2\ \cdots\ B_N$

Output

For each test case, print $N$ integers on one line, separated by spaces.

The $i$ -th integer must be the number of possible completions when $K=i-1$ , modulo $998\ 244\ 353$ .

Constraints

$1 \leq T \leq 1\ 000$ .
$2 \leq N \leq 200\ 000$ .
The sum of $N$ over all test cases is at most .

Subtasks

#	Score	Constraints
1	20	$N \leq 200$ .
2	30	$N \leq 2\ 000$ .
3	50	No additional constraints.

Samples

Input

3
3
2 -1 2
4
2 3 -1 -1
10
2 4 6 8 10 -1 -1 -1 -1 3

Output

2 0
4 0 0
1671 135 1 0 0 0 0 0 0