$cats$ 有一个长度为 $n$ 的排列 $p$，现在他想要在这 $n$ 个数每相邻两个数之间随机加入一个运算符号，符号为加减乘除中的一种（每一种符号的概率相等，均为 $\tfrac{1}{4}$）。添加完符号后这个排列构成了一个表达式，现在 $cats$ 想要知道这个表达式的值的期望。（表达式的计算遵循先乘除后加减，同级运算则按从左到右的顺序依次进行的原则）

现在 $cats$ 的这个排列中一些位置的值被擦去了（用 $p_i=-1$ 表示），$cats$ 想要知道所有可能的排列（每一种可能的排列出现的概率均相同）构成的所有表达式的值的期望对 $998244353$ 取模的结果。

输入格式

第一行一个整数 $t$ $(1\leq t\leq 1000)$，表示测试数据组数。

接下来对于每一组数据，第一行一个整数 $n$ $(1\leq n\leq 2\times 10^5)$，表示排列的长度。

接下来一行包含 $n$ 个由空格隔开的整数 $p_i$ $(p_i=-1 \text{ 或 } 1\leq p_i\leq n)$，表示给出的排列，其中 $p_i=-1$ 表示这个位置被删去了。保证所有不为 $-1$ 的 $p_i$ 互不相同。

保证所有数据的 $n$ 的和不超过 $10^6$。

输出格式

对于每一组数据输出一行，表示所有可能表达式的期望对 $998244353$ 取模的结果。

样例

输入

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

输出

263858861
248609357
811073540
337297410