Với một hoán vị ~a~ ^∗ độ dài ~n~, định nghĩa ma trận MEX của dãy ~a~ là ma trận ~M~ có kích thước ~n \times n~, trong đó giá trị của phần tử ~M_{i, j}~ được xác định như sau:

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

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

Một hoán vị ~a~ độ dài ~n~ được gọi là ~k~-good (~0 \le k < n~) nếu không tồn tại hoán vị ~b~ độ dài ~n~ sao cho:

• Vị trí của phần tử có giá trị ~k~ trong hoán vị ~a~ khác với vị trí của phần tử có giá trị ~k~ trong hoán vị ~b~.

• Ma trận MEX của hai hoán vị ~a~ và ~b~ giống nhau.

Cho dãy số nguyên ~a'_1, a'_2, \ldots, a'_n~ (~-1 \le a'_i < n~). Với mọi ~k~ từ ~0~ đến ~n - 1~, hãy đếm số lượng hoán vị ~a~ độ dài ~n~ thỏa mãn:

• Với mọi ~i~ từ ~1~ đến ~n~, nếu ~a'_i \ne -1~ thì ~a_i = a'_i~;

• ~a~ là hoán vị ~k~-good.

Vì kết quả có thể rất lớn, hãy in ra các đáp án sau khi chia lấy dư cho ~998\ 244\ 353~.

∗ Một hoán vị độ dài ~n~ là dãy số bao gồm ~n~ số nguyên không âm phân biệt có giá trị từ ~0~ đến ~n-1~ được sắp xếp theo thứ tự bất kỳ. Ví dụ, ~[1, 2, 0, 4, 3]~ là một hoán vị có độ dài ~n=5~, tuy nhiên ~[0, 1, 1]~ không phải là hoán vị (~1~ xuất hiện hai lần trong dãy), và ~[2, 1, 3]~ cũng không phải là hoán vị (~n=3~ nhưng lại xuất hiện số ~3~ trong dãy).

† Giá trị ~mex~ của một dãy số nguyên là số nguyên không âm nhỏ nhất không xuất hiện trong dãy. Ví dụ:

• Giá trị ~mex~ của dãy ~[2, 2, 1]~ bằng ~0~, vì ~0~ không xuất hiện trong dãy.

• Giá trị ~mex~ của dãy ~[3, 1, 0, 1]~ bằng ~2~, vì ~0~ và ~1~ xuất hiện trong dãy, nhưng ~2~ thì không.

• Giá trị ~mex~ của dãy ~[0, 3, 1, 2]~ bằng ~4~, vì ~0,1,2,3~ xuất hiện trong dãy, nhưng ~4~ thì không.

Input

Dòng đầu tiên chứa số nguyên ~t~ (~1 \le t \le 5000~) — số lượng test case. Mô tả của mỗi test case như sau:

• Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \le n \le 5000~) — kích thước của dãy ~a'~.

• Dòng thứ hai chứa ~n~ số nguyên ~a'_1, a'_2, \dots, a'_n~ (~-1 \le a'_i < n~). Đảm bảo các phần tử có giá trị không âm chỉ xuất hiện một lần trong dãy ~a'~.

Đảm bảo rằng tổng ~n~ qua tất cả các test case không vượt quá ~5000~.

Output

Với mỗi test case, hãy in ra ~n~ số nguyên, trong đó số thứ ~i~ là số lượng dãy ~a~ thỏa mãn điều kiện đề bài tương ứng với ~k = i - 1~. Vì kết quả có thể rất lớn, hãy in ra các đáp án sau khi chia lấy dư cho ~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

Trong ba test case đầu tiên, có thể chỉ ra rằng tất cả hoán vị độ dài ~n \le 3~ đều là hoán vị ~k~-good với mọi ~k~ từ ~0~ đến ~n - 1~. Vì thế:

• Trong test case thứ nhất, chỉ có ~1~ hoán vị ~a~ có thể tạo ra từ dãy ~a'~ là ~[0]~ nên đáp án cho test case này với ~k = 0~ là ~1~.

• Trong test case thứ hai, chỉ có ~1~ hoán vị ~a~ có thể tạo ra từ dãy ~a'~ là ~[1, 0]~ nên đáp án cho test case này với ~k = 0, 1~ là ~1~.

• Trong test case thứ ba, có ~6~ hoán vị ~a~ có thể tạo ra từ dãy ~a'~ là ~[0, 1, 2]~; ~[0, 2, 1]~; ~[1, 0, 2]~; ~[1, 2, 0]~; ~[2, 0, 1]~ và ~[2, 1, 0]~ nên đáp án cho test case này với ~k = 0, 1, 2~ là ~6~.

Trong test case thứ tư, từ dãy ~a'~ có thể tạo ra hai hoán vị ~a~ khác nhau là: ~[2,3,0,1]~; ~[2,3,1,0]~, với ma trận MEX lần lượt như sau: $$\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}$$

Có thể chỉ ra rằng không có hoán vị ~b \ne a~ nào cho ra hai ma trận MEX trên, nên mọi hoán vị ~a~ tạo được đều là hoán vị ~k~-good với mọi ~k~ từ ~0~ đến ~n - 1~. Đáp án cho test case này với ~k = 0, 1, 2, 3~ đều là ~2~.

Trong test case thứ năm, có thể tạo ra sáu hoán vị ~a~ khác nhau là: ~[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]~ và ~[3, 1, 2, 4, 0]~, với ma trận MEX lần lượt như sau:

$$\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}$$

• Với ~k = 0~ và ~k = 1~, mọi hoán vị ~a~ tạo được đều là hoán vị ~0~-good và ~1~-good nên đáp án là ~6~.

• Với ~k = 2~, đáp án là ~5~ do có hoán vị ~a~ sau không thỏa mãn:

  • Hoán vị ~a = [3, 1, {\color{red}{2}}, 4, 0]~ và ~b = [3, 1, 4, {\color{red}{2}}, 0]~ đều cho ra cùng ma trận MEX, nhưng ~a_2 = b_3 = 2~ ở vị trí khác nhau;

  Các hoán vị ~a~ còn lại đều là hoán vị ~2~-good.

• Với ~k = 3~, đáp án là ~4~. Dưới đây là các cặp dãy ~a~ và ~b~ cho ra cùng ma trận MEX nhưng vị trí của giá trị ~3~ khác nhau:

  • ~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]~

• Với ~k = 4~, đáp án là ~3~. Dưới đây là các cặp dãy ~a~ và ~b~ cho ra cùng ma trận MEX nhưng vị trí của giá trị ~4~ khác nhau:

  • ~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]~