You are given an array a consisting of n integers. Indices of the array start from zero (i. e. the first element is a_0, the second one is a_1, and so on).

You can reverse at most one subarray (continuous subsegment) of this array. Recall that the subarray of a with borders l and r is a[l; r] = a_l, a_{l + 1}, ..., a_{r}.

Your task is to reverse such a subarray that the sum of elements on even positions of the resulting array is maximized (i. e. the sum of elements a_0, a_2, ..., a_{2k} for integer k = ⌊(n-1)/(2)⌋ should be maximum possible).

You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1 ≤ t ≤ 2 ⋅ 10^4) — the number of test cases. Then t test cases follow.

The first line of the test case contains one integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the length of a. The second line of the test case contains n integers a_0, a_1, ..., a_{n-1} (1 ≤ a_i ≤ 10^9), where a_i is the i-th element of a.

It is guaranteed that the sum of n does not exceed 2 ⋅ 10^5 (∑ n ≤ 2 ⋅ 10^5).

Output

For each test case, print the answer on the separate line — the maximum possible sum of elements on even positions after reversing at most one subarray (continuous subsegment) of a.

Example

Input


4
8
1 7 3 4 7 6 2 9
5
1 2 1 2 1
10
7 8 4 5 7 6 8 9 7 3
4
3 1 2 1


Output


26
5
37
5
import java.util.*;
import java.io.*;

public class File {
    public static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }
    }
	
    public static void main(String[] args) {
        FastScanner sc = new FastScanner();
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
		
		
		
		
		
		/*
		Length must be even.
		Total = all evens in array + (odds in range - evens in range)		
		Maximize (odds - evens) in range.		
		Precompute the prefix sums of these.
		
		
		We can calculate separately for even length arrays starting on odd indices.
		Then calculate for even length arrays starting on even indices.
		Prefix will equal odd total - even total.
		*/
		
		
		int T = sc.nextInt();
		
		for (int t = 1; t <= T; t++) {
			int n = sc.nextInt();
			long[] a = new long[n];
			
			long evenSum = 0L;
			
			for (int i = 0; i < n; i++) {
				a[i] = sc.nextLong();
				
				if (i % 2 == 0) {
					evenSum += a[i];
				}
			}
			
			long[] preOdds = new long[n];
			long[] preEvens = new long[n];
			
			long[] preEvenIndex = new long[n];
			
			for (int i = 0; i < n; i++) {
				if (i % 2 == 0) {
					preEvens[i] = (i > 0 ? preEvens[i-1] : 0) + a[i];
					preOdds[i] = (i > 0 ? preOdds[i-1] : 0);
				}
				else {
					preOdds[i] = preOdds[i-1] + a[i];
					preEvens[i] = preEvens[i-1];
				}
			}
			
			// Ending on even indices.
			long oddTotal = 0;
			long evenTotal = 0;
			for (int i = 2; i < n; i += 2) {
				evenTotal += a[i];
				oddTotal += a[i-1];
				preEvenIndex[i] = oddTotal - evenTotal;	
			}
			
			
			// Ending on odd indices.
			long[] preOddIndex = new long[n];
			
			oddTotal = 0;
			evenTotal = 0;
			for (int i = 1; i < n; i += 2) {
				oddTotal += a[i];
				evenTotal += a[i-1];
				preOddIndex[i] = oddTotal - evenTotal;
			}
			
			
			
			// 3 1 2 1
			// presums: 0, 
			// at index 2, pre = -1
			// min pre = 0
			// max = Math.max(max, -1 - 0)
			
			// For odd indices as the end.
			// presums: 0, 
			// at index 1, pre = -2
			// min pre = 0
			// Max = Math.max(max, totalEven + (-2 - 0))
			// at index 3, pre = -3
			// min pre = -2
			// Max = Math.max(max, totalEven + -1))			
			
			// Initially, with no swaps made.
			long max = evenSum;
			
			// Total = all evens in array + (odds in range - evens in range)
			TreeSet<Long> preSums = new TreeSet<Long>();
			preSums.add(0L); // Ignore index 0 element 
			
			// Find answer where the swap takes place on an even index.
			for (int i = 2; i < n; i += 2) {							
				// Find the mininum prefix sum, so that the current - that is maximized.
				long currTotal = preEvenIndex[i];
				Long min = preSums.first();
				max = Math.max(max, evenSum + currTotal - min);	
				preSums.add(currTotal);
			}

			preSums.clear();
			preSums.add(0L);
			// Find answer where the swap takes place on an odd index.
			for (int i = 1; i < n; i += 2) {
				long currTotal = preOddIndex[i];
				Long min = preSums.first();
				max = Math.max(max, evenSum + currTotal - min);
				preSums.add(currTotal);				
			}
			
			
			
			
			out.println(max);
		}
		
		
		
		
		
		
		out.close();
	}
}








