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.*;
import java.lang.Math;
import java.util.Random;


public class Solution{


	public static void main(String[] args) throws Exception{

		FastScanner fs = new FastScanner();
		
		int t = fs.nextInt();

		while(t-->0){
			int n = fs.nextInt();
			long[] arr = new long[n];

			for(int i=0;i<n;i++) arr[i] = fs.nextLong();

			long sum = 0;
			for(int i=0;i<n;i+=2)
				sum += arr[i];

			int n1 = n/2;
			int n2 = (n-1)/2;
			long[] v1 = new long[n1];
			long[] v2 = new long[n2];

			for(int i=0;i<n1;i++){
				v1[i] = arr[2*i+1] - arr[2*i];
			}

			for(int i=0;i<n2;i++){
				v2[i] = arr[2*i+1] - arr[2*(i+1)];
			}

			System.out.println(sum + Math.max(maxSum(v1), maxSum(v2)));


		}

			
		
	}

	static long maxSum(long[] arr){
		int n = arr.length;
		long ans = 0;
		long sum = 0;
		for(int i=0;i<n;i++){
			if(arr[i]<0){
				ans = Math.max(ans, sum);
			}
			sum = sum + arr[i];
			if(sum<0)
				sum = 0;
		}
		ans = Math.max(ans, sum);
		return ans;
	}

	static class FastScanner{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");

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

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

		public int[] readArray(int n){
			int[] a = new int[n];
			for(int i=0;i<n;i++)
				a[i] = nextInt();
			return a;
		}

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

	}

}