B"Define the beauty value of a sequence b_1,b_2, ldots,b_c as the maximum value of sum limits_{i=1}^{q}b_i + sum limits_{i=s}^{t}b_i , where q , s , t are all integers and s > q or t <= q q . Note that b_i = 0 when i<1 or i>c , sum limits_{i=s}^{t}b_i = 0 when s>t . For example, when b = [-1,-2,-3] , we may have q = 0 , s = 3 , t = 2 so the beauty value is 0 + 0 = 0 . And when b = [-1,2,-3] , we have q = s = t = 2 so the beauty value is 1 + 2 = 3 . You are given a sequence a of length n , determine the sum of the beauty value of all non-empty subsegments a_l,a_{l+1}, ldots,a_r ( 1 <= q l <= q r <= q n ) of the sequence a . Print the answer modulo 998 ,244 ,353 . Each test contains multiple test cases. The first line contains an integer T ( 1 <= T <= 10^4 ) -- the number of test cases. The first line contains an integer n ( 1 <= n <= 10^6 ) -- the length of a . The second line contains n integers a_1,a_2, ldots,a_n ( -10^6 <= q a_i <= q 10^6 ) -- the given sequence. It's guaranteed that the sum of n does not exceed 10^6 . For each test case, print a line containing a single integer -- the answer modulo 998 ,244 ,353 . In the second test case, for the subsequence [-26,43,-41,34,13] , when q=5 , s=2 , t=5 , sum limits_{i=1}^{q}b_i + sum limits_{i=s}^{t}b_i = 23 + 49 = 72 . In the third test case, there is only one non-empty consecutive subsequence [74] . When q=1 , s=1 , t=1 , sum limits_{i=1}^{q}b_i + sum limits_{i=s}^{t}b_i = 148 . "...