For a permutation ~a~ ^∗ of length ~n~, define the MEX matrix of the sequence ~a~ as the matrix ~M~ of size ~n \times n~, where the value of element ~M_{i, j}~ is determined as follows:

• ~M_{i, j} = mex\left(a_i, a_{i + 1}, \dots, a_j\right)~ ^† for ~i \le j~;

• ~M_{i, j} = -1~ for ~i > j~.

A permutation ~a~ of length ~n~ is called ~k~-good (~0 \le k < n~) if there does not exist a permutation ~b~ of length ~n~ such that:

• The position of the element with value ~k~ in permutation ~a~ is different from the position of the element with value ~k~ in permutation ~b~.

• The MEX matrices of the two permutations ~a~ and ~b~ are the same.

You are given an integer sequence ~a'_1, a'_2, \ldots, a'_n~ (~-1 \le a'_i < n~). For every ~k~ from ~0~ to ~n - 1~, count the number of permutations ~a~ of length ~n~ such that:

• For every ~i~ from ~1~ to ~n~, if ~a'_i \ne -1~ then ~a_i = a'_i~;

• ~a~ is a ~k~-good permutation.

Since the answer may be very large, output the answers modulo ~998\ 244\ 353~.

∗ A permutation of length ~n~ is a sequence consisting of ~n~ distinct non-negative integers with values from ~0~ to ~n-1~, arranged in any order. For example, ~[1, 2, 0, 4, 3]~ is a permutation of length ~n=5~, however ~[0, 1, 1]~ is not a permutation (~1~ appears twice in the sequence), and ~[2, 1, 3]~ is also not a permutation (~n=3~ but the number ~3~ appears in the sequence).

† The ~mex~ of an integer sequence is the smallest non-negative integer that does not appear in the sequence. For example:

• The ~mex~ of the sequence ~[2, 2, 1]~ is ~0~, because ~0~ does not appear in the sequence.

• The ~mex~ of the sequence ~[3, 1, 0, 1]~ is ~2~, because ~0~ and ~1~ appear in the sequence, but ~2~ does not.

• The ~mex~ of the sequence ~[0, 3, 1, 2]~ is ~4~, because ~0,1,2,3~ appear in the sequence, but ~4~ does not.

Input

The first line contains an integer ~t~ (~1 \le t \le 5000~) — the number of test cases. The description of each test case is as follows:

• The first line contains a positive integer ~n~ (~1 \le n \le 5000~) — the size of the sequence ~a'~.

• The second line contains ~n~ integers ~a'_1, a'_2, \dots, a'_n~ (~-1 \le a'_i < n~). It is guaranteed that non-negative elements appear at most once in the sequence ~a'~.

It is guaranteed that the sum of ~n~ over all test cases does not exceed ~5000~.

Output

For each test case, print ~n~ integers, where the ~i~-th integer is the number of sequences ~a~ satisfying the conditions of the statement for ~k = i - 1~. Since the answer may be very large, output the answers modulo ~998\ 244\ 353~.

Scoring

Sample Input 1

6
1
-1
2
-1 0
3
-1 -1 -1
4
2 3 -1 -1
5
-1 1 -1 4 -1
6
3 -1 5 4 -1 -1

Sample Output 1

1 
1 1 
6 6 6 
2 2 2 2 
6 6 5 4 3 
6 6 4 6 0 0

Notes

In the first three test cases, it can be shown that all permutations of length ~n \le 3~ are ~k~-good permutations for all ~k~ from ~0~ to ~n - 1~. Therefore:

• In the first test case, only ~1~ permutation ~a~ can be constructed from the array ~a'~, which is ~[0]~, so the answer for this test case with ~k = 0~ is ~1~.

• In the second test case, only ~1~ permutation ~a~ can be constructed from the array ~a'~, which is ~[1, 0]~, so the answer for this test case with ~k = 0, 1~ is ~1~.

• In the third test case, there are ~6~ permutations ~a~ that can be constructed from the array ~a'~: ~[0, 1, 2]~; ~[0, 2, 1]~; ~[1, 0, 2]~; ~[1, 2, 0]~; ~[2, 0, 1]~ and ~[2, 1, 0]~, so the answer for this test case with ~k = 0, 1, 2~ is ~6~.

In the fourth test case, from the array ~a'~ we can construct two different permutations ~a~: ~[2,3,0,1]~ and ~[2,3,1,0]~, with the following MEX matrices respectively: $$\begin{array}{cc} \begin{array}{|r|r|r|r|} \hline 0 & 0 & 1 & 4 \\ \hline \color{grey}{-1} & 0 & 1 & 2 \\ \hline \color{grey}{-1} & \color{grey}{-1} & 1 & 2 \\ \hline \color{grey}{-1} & \color{grey}{-1} & \color{grey}{-1} & 0 \\ \hline \end{array} & \begin{array}{|r|r|r|r|} \hline 0 & 0 & 0 & 4 \\ \hline \color{grey}{-1} & 0 & 0 & 2 \\ \hline \color{grey}{-1} & \color{grey}{-1} & 0 & 2 \\ \hline \color{grey}{-1} & \color{grey}{-1} & \color{grey}{-1} & 1 \\ \hline \end{array} \\ \end{array}$$

It can be shown that no permutation ~b \ne a~ produces either of the two MEX matrices above, so every permutation ~a~ that can be constructed is a ~k~-good permutation for all ~k~ from ~0~ to ~n - 1~. The answer for this test case with ~k = 0, 1, 2, 3~ is ~2~.

In the fifth test case, six different permutations ~a~ can be constructed: ~[0, 1, 2, 4, 3]~; ~[0, 1, 3, 4, 2]~; ~[2, 1, 0, 4, 3]~; ~[2, 1, 3, 4, 0]~; ~[3, 1, 0, 4, 2]~ and ~[3, 1, 2, 4, 0]~, with the following MEX matrices respectively:

$$\begin{array}{ccccc} \begin{array}{|r|r|r|r|r|} \hline 1 & 2 & 3 & 3 & 5 \\ \hline \color{grey}{-1} & 0 & 0 & 0 & 0 \\ \hline \color{grey}{-1} & \color{grey}{-1} & 0 & 0 & 0 \\ \hline \color{grey}{-1} & \color{grey}{-1} & \color{grey}{-1} & 0 & 0 \\ \hline \color{grey}{-1} & \color{grey}{-1} & \color{grey}{-1} & \color{grey}{-1} & 0 \\ \hline \end{array} & \begin{array}{|r|r|r|r|r|} \hline 1 & 2 & 2 & 2 & 5 \\ \hline \color{grey}{-1} & 0 & 0 & 0 & 0 \\ \hline \color{grey}{-1} & \color{grey}{-1} & 0 & 0 & 0 \\ \hline \color{grey}{-1} & \color{grey}{-1} & \color{grey}{-1} & 0 & 0 \\ \hline \color{grey}{-1} & \color{grey}{-1} & \color{grey}{-1} & \color{grey}{-1} & 0 \\ \hline \end{array} & \begin{array}{|r|r|r|r|r|} \hline 0 & 0 & 3 & 3 & 5 \\ \hline \color{grey}{-1} & 0 & 2 & 2 & 2 \\ \hline \color{grey}{-1} & \color{grey}{-1} & 1 & 1 & 1 \\ \hline \color{grey}{-1} & \color{grey}{-1} & \color{grey}{-1} & 0 & 0 \\ \hline \color{grey}{-1} & \color{grey}{-1} & \color{grey}{-1} & \color{grey}{-1} & 0 \\ \hline \end{array} & \end{array}$$

$$\begin{array}{ccccc} \begin{array}{|r|r|r|r|r|} \hline 0 & 0 & 0 & 0 & 5 \\ \hline \color{grey}{-1} & 0 & 0 & 0 & 2 \\ \hline \color{grey}{-1} & \color{grey}{-1} & 0 & 0 & 1 \\ \hline \color{grey}{-1} & \color{grey}{-1} & \color{grey}{-1} & 0 & 1 \\ \hline \color{grey}{-1} & \color{grey}{-1} & \color{grey}{-1} & \color{grey}{-1} & 1 \\ \hline \end{array} & \begin{array}{|r|r|r|r|r|} \hline 0 & 0 & 2 & 2 & 5 \\ \hline \color{grey}{-1} & 0 & 2 & 2 & 3 \\ \hline \color{grey}{-1} & \color{grey}{-1} & 1 & 1 & 1 \\ \hline \color{grey}{-1} & \color{grey}{-1} & \color{grey}{-1} & 0 & 0 \\ \hline \color{grey}{-1} & \color{grey}{-1} & \color{grey}{-1} & \color{grey}{-1} & 0 \\ \hline \end{array} & \begin{array}{|r|r|r|r|r|} \hline 0 & 0 & 0 & 0 & 5 \\ \hline \color{grey}{-1} & 0 & 0 & 0 & 3 \\ \hline \color{grey}{-1} & \color{grey}{-1} & 0 & 0 & 1 \\ \hline \color{grey}{-1} & \color{grey}{-1} & \color{grey}{-1} & 0 & 1 \\ \hline \color{grey}{-1} & \color{grey}{-1} & \color{grey}{-1} & \color{grey}{-1} & 1 \\ \hline \end{array} & \end{array}$$

• For ~k = 0~ and ~k = 1~, every permutation ~a~ that can be constructed is a ~0~-good and ~1~-good permutation, so the answer is ~6~.

• For ~k = 2~, the answer is ~5~ since the following permutation ~a~ does not satisfy the condition:

  • Permutation ~a = [3, 1, {\color{red}{2}}, 4, 0]~ and ~b = [3, 1, 4, {\color{red}{2}}, 0]~ both produce the same MEX matrix, but ~a_2 = b_3 = 2~ are at different positions.

  The remaining permutations ~a~ are all ~2~-good permutations.

• For ~k = 3~, the answer is ~4~. Below are the pairs of arrays ~a~ and ~b~ that produce the same MEX matrix but have the value ~3~ at different positions:

  • ~a = [0, 1, {\color{red}{3}}, 4, 2]~, ~b = [0, 1, 4, {\color{red}{3}}, 2]~

  • ~a = [2, 1, {\color{red}{3}}, 4, 0]~, ~b = [2, 1, 4, {\color{red}{3}}, 0]~

• For ~k = 4~, the answer is ~3~. Below are the pairs of arrays ~a~ and ~b~ that produce the same MEX matrix but have the value ~4~ at different positions:

  • ~a = [0, 1, 3, {\color{red}{4}}, 2]~, ~b = [0, 1, {\color{red}{4}}, 3, 2]~

  • ~a = [2, 1, 3, {\color{red}{4}}, 0]~, ~b = [2, 1, {\color{red}{4}}, 3, 0]~

  • ~a = [3, 1, 2, {\color{red}{4}}, 0]~, ~b = [3, 1, {\color{red}{4}}, 2, 0]~