题目描述

RT，现在有一个简单的贡献最大问题。

小Y作为一个算法爱好者。现在和小S在玩一个游戏.这个游戏的具体内容是这样的：

给你一个$n$个数的序列，分别为$a_1,a_2,...,a_{n-1},a_n$，保证$a_i\in[-2,2]$。

你能对该序列进行两次操作。

操作1：删除该序列的前$L$个数字(必须按顺序删除)。注意，L可以为0。

操作2：删除该序列的后$R$个数字(必须按顺序删除)。注意，R可以为0。

如果小Y操作后的序列的数字的乘积大于等于小S操作后的序列的数字的乘积，那么小Y就能获得本次游戏的胜利。

因为小S很聪明，所以小Y只有保证自己的答案最大才放心，那么小Y该如何操作呢？

特殊的，对于空数组来说，我们定义它的值为$1$。

输入格式

本题为多组输入，第一行输入一个$T$，表示有$T$组数据。

接下来$T$组数据，每组数据第一行，输入一个数$n$，表示有$n$个数。

接下来一行输入$n$个数字，表示$a_i$。

数据保证，$T\in[1,50],n\in[1,2 \times 10^5],a_i\in[-2,2]$。

输出格式

输出$T$行，对于每一组数据，输出对应的最大值，因为最大值可能很大，所以你需要将最终答案对$998244353$取模后再输出。

每组数据输出完之后需换行。

样例:

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

2
1
4
2
4