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.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.Vector;

public class anyproblem {
    static int p = 1000000007;
    //static long dp[][]=new long[20003][20003];

    public static void main(String[] args) throws Exception {
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(java.io.FileDescriptor.out), "ASCII"), 512);
        FastReader sc = new FastReader();
        StringBuilder sb = new StringBuilder();
        long t = sc.nextLong();
        while (t-- > 0) {
        int n=sc.nextInt();
        long ar[]=new long[n];
        for(int i=0;i<n;i++)
        {
            ar[i]=sc.nextLong();

        }

        long e=0,o=0,oe=0;
        for(int i=0;i<n;i++)
        {
            if(i%2==0)
                e+=ar[i];
            else
                o+=ar[i];
        }
        long ear[]=new long[n/2];
        long oar[]=new long[(n-1)/2];
        int c=0;
        for(int i=0;i<n;i+=2)
        {
            if(i+1<n)
        ear[c++]=ar[i+1]-ar[i];
        }
         c=0;
        for(int i=1;i<n;i+=2)
        {
            if(i+1<n)
            oar[c++]=ar[i]-ar[i+1];
        }
         //   System.out.println(Arrays.toString(ear));
          //  System.out.println(Arrays.toString(oar));

            long max=Integer.MIN_VALUE;
            long s=0;
            for(int i=0;i<ear.length;i++)
            {
                s=Math.max(ear[i],s+ear[i]);
                max=Math.max(s,max);
            }
            s=0;
            for(int i=0;i<oar.length;i++)
            {
                s=Math.max(oar[i],s+oar[i]);
                max=Math.max(s,max);
            }
            max=Math.max(e,e+max);
            // max=Math.max(max,ans(ar,0,n-1,o,e));

           System.out.println(max);
        }
        out.write(sb.toString());
        out.flush();
    }
    public static long ans(long ar[],int l,int r,long o,long e)
    {

        if(l==r||l>r)
            return 0;

        if(l%2==0&&r%2==0)
        {
            long h=Math.max(ar[l]+ans(ar,l+1,r,o,e-ar[l]),ar[r]+ans(ar,l,r-1,o,e-ar[r]));;
            System.out.println(l+" "+r+"  "+h+" o-e "+ (o-e));
            return h;
        }
        else if(l%2!=0&&r%2!=0)
        {
            long h=Math.max(ans(ar,l+1,r,o-ar[l],e),ans(ar,l,r-1,o-ar[r],e));
            System.out.println(l+" "+r+"  "+h+" o-e "+ (o-e));
            return  h;
        }
        else if(l%2==0&&r%2!=0)
        {
            long h= Math.max(o>e?o:Integer.MIN_VALUE,Math.max(ar[l]+ans(ar,l+1,r,o,e-ar[l]),ans(ar,l,r-1,o-ar[r],e)));
            System.out.println(l+" "+r+"  "+h+" o-e "+ (o-e));
            return h;
        }
        else
        {
            long h=Math.max(o>e?o:Integer.MIN_VALUE,Math.max(ans(ar,l+1,r,o-ar[l],e),ar[r]+ans(ar,l,r-1,o,e-ar[r])));
            System.out.println(l+" "+r+"  "+h+" o-e "+ (o-e));
            return h;
        }
    }





        ///////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////
        static class FastReader {

            BufferedReader br;
            StringTokenizer st;

            public FastReader() {
                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());
            }

            String nextLine() {
                String str = "";
                try {
                    str = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                return str;
            }
        }


    }

