题目描述

'Cause morning rolls around, and it's another day of sun!

但是作为一个睡瘾患者，肖恩经常睡觉睡个半天，因此，当他醒来时，他甚至记不清今天是星期几。

所以从某一天开始，他开始进行记录：每次他醒来的时候，他就会写下一个数字，表示此时外面是否有阳光。如果有，他会写一个 1；否则，他会写一个 0。在完成记录后，还没等太阳下山，或是太阳升起，他又再次入睡。假设每次肖恩醒来时，他看到的要么是阳光，要么是月光，但不会同时看到两者。

这些记录下来的数字实际上形成了一个长度为 $n$ 的数组：$[a_1, a_2, \ldots, a_n]$ ($1 \leq i \leq n, 0 \leq a_i \leq 1$)，其中 $a_i$ 表示肖恩写下的第 $i$ 个数字。

然而，随着时间的推移，一些写下的数字变得模糊不清，你无法判断它是 1 还是 0。如果有 $k$ 个数字无法识别，则可能有 $2^k$ 种不同的数组。

对于每个可能的数组，你都可以依据这个数组计算肖恩看到阳光的最小天数。如果将可能的不同数组的最小天数结果相加，得到的结果如何呢？由于答案可能很大，请将结果关于 $998 244353$ 取模后输出。

输入格式

每组测试包含多个测试用例。第一行是测试用例的数量 $T (1 \leq T \leq 10^4)$。

每个测试用例由两行组成。

第一行包含一个整数 $n (2 \leq n \leq 5 \times 10^5)$，表示笔记的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n (-1 \leq a_i \leq 1)$，表示每个记录下来的数字。只有当 $a_i = -1$ 时，数字是未知的。

可以保证单组测试中，$\sum n$ 不会超过 $5 \times 10^5$。

输出格式

3
3
1 0 1
3
0 0 0
3
1 -1 1

2
0
3

解释 #1

在第一个测试用例中，当肖恩记录第一个和第三个数字 $1$ 时，他看到的阳光一定是两个不同的天的。

在第二个测试用例中，肖恩从未看到阳光，因此答案是 $0$。

在第三个测试用例中，数组可能是 $[1, 1, 1]$ 或 $[1, 0, 1]$。如果数组是 $[1, 1, 1]$，那么这些数字可能都是同一天被记录下来的，因此结果是1。如果数组是 $[1, 0, 1]$，那么与第一个测试用例一致，结果为 $2$。将两种情况的答案求和，结果是 $1 + 2 = 3$。