B'Polycarp found under the Christmas tree an array a of n elements and instructions for playing with it: For example, if n = 5 and a = [7, 3, 1, 2, 3] , then the following game options are possible: Help Polycarp to find out the maximum score he can get if he chooses the starting index in an optimal way. The first line contains one integer t ( 1 <= q t <= q 10^4 ) -- the number of test cases. Then t test cases follow. The first line of each test case contains one integer n ( 1 <= q n <= q 2 cdot 10^5 ) -- the length of the array a . The next line contains n integers a_1, a_2, ... , a_n ( 1 <= q a_i <= q 10^9 ) -- elements of the array a . It is guaranteed that the sum of n over all test cases does not exceed 2 cdot 10^5 . For each test case, output on a separate line one number -- the maximum score that Polycarp can get by playing the game on the corresponding array according to the instruction from the statement. Note that Polycarp chooses any starting position from 1 to n in such a way as to maximize his result. The first test case is explained in the statement. In the second test case, the maximum score can be achieved by choosing i = 1 . In the third test case, the maximum score can be achieved by choosing i = 2 . In the fourth test case, the maximum score can be achieved by choosing i = 1 . '...