You are given an array A of size n. In one move, you can select a subarray of size 3. Let those indices be i - 1, i and i + 1. We add A[i] to our total score and then change A[i], A[i - 1] and A[i + 1] to 0. We repeat this process untill the entire array becomes 0. If we select the subarrays optimally, what is the maximum score that can be achieved?
See sample case for better understanding
Input format:
First line contains one integer t, denoting the number of test cases.
Each testcase is provided as follows:-
First line contains one integer n, denoting the size of array.
Next line contains n integers (a1, a2, ... an), representing the array.
Output format:
For each test case, print the maximum achievable score in a new line.
Constraints:
1 <= t <= 5
3 <= n <= 100000(1e5)
1 <= ai <= 1000000000(1e9)
In first case, it will be optimal to select subarrays with i = 2 and i = 4. So our score will be 3 + 4 = 7. Note that here we are considering1-based indices.
In second case, it will be optimal to select subarrays with i = 3 first and then i = 2. So, our score will be 4 + 0 = 4. Note that we can't select subarrays with i = 0 or i = n, as there will be no subarray of size 3 with i = 0 and i = n.
