You are given an array of (n) integers (a_1, a_2, \ldots, a_n). The value of an array is the sum of the maximums of each prefix of the array. More formally, the value of an array (a) is (\sum_{i=1} ^{n} \operatorname{max}(a_1, \ldots, a_i)). For example, the value of the array (1, 2, 1) is (\operatorname{max}(1) + \operatorname{max}(1, 2) + \operatorname{max}(1, 2, 1) = 1 + 2 + 2 = 5). You can choose two indices (i) and (j) and swap elements (a_i) and (a_j); this operation can be applied at most one time. Find the maximum possible value of the array (a) after at most one operation. The first line of the input contains a single integer (t) ((1 \leq t \leq 100)) — the number of test cases. The first line of each test case contains a single integer (n) ((2 \le n \le 50)) — the length of the array (a). The second line contains (n) integers (a_1, a_2, \ldots, a_n) ((1 \le a_i \le 10^4)) — the array (a). For each test case, output the maximum possible value of the array (a) after the swap has been performed. For the first test case, we can swap (a_1) with (a_4) to get the array (5, 1, 4, 2, 3), which has a value of (\operatorname{max}(5) + \operatorname{max}(5, 1) + \operatorname{max}(5, 1, 4) + \operatorname{max}(5, 1, 4, 2) + \operatorname{max}(5, 1, 4, 2, 3) = 25). For the second test case, the current value of the array is (\operatorname{max}(5) + \operatorname{max}(5, 1) = 10). If we were to swap (a_1) and (a_2), (a) would be equal to (1, 5), which has a value of (\operatorname{max}(1) + \operatorname{max}(1, 5) = 6), meaning the best option is to not perform a swap.