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.math.*;
public class DEdu90{

    public static void main(String args[]){
        FastReader sc = new FastReader();
        StringBuilder sb=new StringBuilder();
        int t,i,n;
        t=sc.nextInt();
        while(t-->0){
			n=sc.nextInt();
			long a[]=new long[n];
			long sum=0;
			long dp[][]=new long[n][3]; // editorial solution

			for(i=0;i<n;i++){
				a[i]=sc.nextLong();
			}
			dp[0][0]=a[0];
			dp[0][1]=a[0];
			dp[0][2]=a[0];
			for(i=1;i<n;i++){
				dp[i][0]=i%2==1?dp[i-1][0]:dp[i-1][0]+a[i];
				if(i-2>=0){
					long temp1 = dp[i-2][1] + (i%2==1? a[i]:a[i-1]);
					long temp2 = dp[i-2][0] + a[i-1];
					dp[i][1]=Math.max(temp1,temp2);
				}
				else  if(i-2<0)
					dp[i][1]=Math.max(dp[i-1][0],a[i]);
				dp[i][2]=Math.max(dp[i-1][0],Math.max(dp[i-1][1],dp[i-1][2]))+(i%2==0?a[i]:0);
			}
			//for(i=0;i<n;i++)
			//	out.println(dp[i][0]+" "+dp[i][1]+" "+dp[i][2]);
			sb.append(Math.max(dp[n-1][0],Math.max(dp[n-1][1],dp[n-1][2]))).append('\n');
			
        }
        sb.deleteCharAt(sb.length()-1);
        out.println(sb);
    }

    static PrintWriter out;
    static class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br=new BufferedReader(new InputStreamReader(System.in));
            out=new PrintWriter(System.out,true);
        }
        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());
        }
        String nextLine(){
            String str = "";
            try{
                str=br.readLine();
            }
            catch(IOException e){
                e.printStackTrace();
            }
            return str;
        }
    }

    public static boolean isPrime(int n) {
        if(n<2) return false;
        for(int i=2;i<=(int)Math.sqrt(n);i++) {
            if(n%i==0) return false;
        }
        return true;
    }

    public static void print(int a[],int l,int r){
        int i;
        for(i=l;i<=r;i++)
            out.print(a[i]+" ");
        out.println();
    }

    public static long fastexpo(long x, long y, long p){
        long res=1;
        while(y > 0){
            if((y & 1)==1)
                res= ((res%p)*(x%p))%p;
            y= y >> 1;			
            x = ((x%p)*(x%p))%p;
        }
        return res;
    }

    public static boolean[] sieve (int n) {
        boolean primes[]=new boolean[n+1];
        Arrays.fill(primes,true);
        primes[0]=primes[1]=false;
        for(int i=2;i*i<=n;i++){
            if(primes[i]){
                for(int j=i*i;j<=n;j+=i)
                    primes[j]=false;
            }
        }
        return primes;
    }

    public static long gcd(long a,long b){
        return (BigInteger.valueOf(a).gcd(BigInteger.valueOf(b))).longValue();
    }

    public static void merge(long a[],int l,int m,int r){
        int n1,n2,i,j,k;
        n1=m-l+1;
        n2=r-m;

        long L[]=new long[n1];
        long R[]=new long[n2];

        for(i=0;i<n1;i++)
            L[i]=a[l+i];
        for(j=0;j<n2;j++)
            R[j]=a[m+1+j];

        i=0;j=0;

        k=l;
        while(i<n1&&j<n2){
            if(L[i]<=R[j]){
                a[k]=L[i];
                i++;
            }
            else{
                a[k]=R[j];
                j++;
            }
            k++;
        }

        while(i<n1){
            a[k]=L[i];
            i++;
            k++;
        }
        while(j<n2){
            a[k]=R[j];
            j++;
            k++;
        }
    }
    public static void sort(long a[],int l,int r){
        int m;
        if(l<r){
            m=(l+r)/2;
            sort(a,l,m);
            sort(a,m+1,r);
            merge(a,l,m,r);
        }
    }
}
