Nick is learning how to do yoga. Over the course of the next ~N~ days, he will pick a contiguous nonempty block of days and do yoga during all of them. Each day has a score associated with it. The score of the yoga interval is equal to the product of all the scores of the days when Nick did yoga.
Compute the maximum possible score Nick can get.
~1 \le T \le 10^5~
~1 \le N \le 10^6~
The sum of ~N~ over all test cases is at most ~10^6~.
~|s_i| \le 2~
The first line contains a single positive integer, ~T~, the number of test cases. ~T~ test cases follow.
Each test case starts with a line containing a single positive integer ~N~. The next line contains ~N~ space-separated integers, the ~s_i~ values representing the scores of the ~N~ days in order.
Output the answers for the ~T~ test cases in order. There should be no blank lines in your output.
The answer for the ~i~th test case should be on the ~i~th line. If ~M~ is the maximum score that Nick can attain when doing yoga, output ~M~ modulo 998244353. Note that you are trying to maximize ~M~, not ~M~ modulo 998244353.
2 3 2 -2 2 30 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2