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.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.util.*;
import java.util.concurrent.LinkedBlockingDeque;
import java.io.FileWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;


// graph, dfs,bfs, get connected components,iscycle, isbipartite, dfs on trees



public class scratch_25{
    static class Graph{

        public static class Vertex{
            HashMap<Integer,Long> nb= new HashMap<>();     // for neighbours of each vertex
        }

        public static HashMap<Integer,Vertex> vt;   // for vertices(all)

        public Graph(){
            vt= new HashMap<>();
        }

        public static int numVer(){
            return vt.size();
        }

        public static boolean contVer(int ver){
            return vt.containsKey(ver);
        }

        public static void addVer(int ver){
            Vertex v= new Vertex();
            vt.put(ver,v);
        }






        public static void addEdge(int ver1, int ver2, long weight){
            if(!vt.containsKey(ver1) || !vt.containsKey(ver2)){
                return;
            }
            Vertex v1= vt.get(ver1);
            Vertex v2= vt.get(ver2);
            v1.nb.put(ver2,(long)weight);                                 // if previously there is an edge, then this replaces that edge
            v2.nb.put(ver1,(long)weight);
        }

        public static void delEdge(int ver1, int ver2){

            if(!vt.containsKey(ver1) || !vt.containsKey(ver2)){
                return;
            }
            vt.get(ver1).nb.remove(ver2);
            vt.get(ver2).nb.remove(ver1);
        }
        public static void delVer(int ver){
            if(!vt.containsKey(ver)){
                return;
            }
            Vertex v1= vt.get(ver);
            ArrayList<Integer> arr= new ArrayList<>(v1.nb.keySet());
            for (int i = 0; i <arr.size() ; i++) {
                int s= arr.get(i);
                vt.get(s).nb.remove(ver);
            }
            vt.remove(ver);
        }
        static boolean done[];
        static int parent[];
        static ArrayList<Integer>vals= new ArrayList<>();


        public static boolean isCycle(int i){
            Stack<Integer>stk= new Stack<>();

            stk.push(i);
            while(!stk.isEmpty()){
                int x= stk.pop();
                vals.add(x);
                //   System.out.print("current="+x+" stackinit="+stk);
                if(!done[x]){
                    done[x]=true;
                }
                else if(done[x] ){
                    return true;
                }

                ArrayList<Integer>ar= new ArrayList<>(vt.get(x).nb.keySet());
                for (int j = 0; j <ar.size() ; j++) {
                    if(parent[x]!=ar.get(j)){
                        parent[ar.get(j)]=x;
                        stk.push(ar.get(j));
                    }
                }
                // System.out.println(" stackfin="+stk);
            }
            return false;
        }
        static int[]level;
        static int[] curr;
        static int[] fin;

        public static void dfs(int src){
            done[src]=true;
            level[src]=0;
            Queue<Integer>q= new LinkedList<>();
            q.add(src);
            while(!q.isEmpty()){
                int x= q.poll();
                ArrayList<Integer>arr= new ArrayList<>(vt.get(x).nb.keySet());
                for (int i = 0; i <arr.size() ; i++) {
                    int v= arr.get(i);
                    if(!done[v]){
                        level[v]=level[x]+1;
                        done[v]=true;
                        q.offer(v);
                    }
                }
            }
        }
        static int oc[];
        static int ec[];


        public static void dfs1(int src){
            Queue<Integer>q= new LinkedList<>();
            q.add(src);
            done[src]= true;
            //    int count=0;
            while(!q.isEmpty()){

                int x= q.poll();
                //   System.out.println("x="+x);
                int even= ec[x];
                int odd= oc[x];
                if(level[x]%2==0){
                    int val= (curr[x]+even)%2;
                    if(val!=fin[x]){
                        //  System.out.println("bc");
                        even++;
                        vals.add(x);
                    }
                }
                else{
                    int val= (curr[x]+odd)%2;
                    if(val!=fin[x]){
                        //   System.out.println("bc");
                        odd++;
                        vals.add(x);
                    }

                }
                ArrayList<Integer>arr= new ArrayList<>(vt.get(x).nb.keySet());
                //   System.out.println(arr);
                for (int i = 0; i <arr.size() ; i++) {
                    int v= arr.get(i);
                    if(!done[v]){
                        done[v]=true;
                        oc[v]=odd;
                        ec[v]=even;
                        q.add(v);
                    }
                }
            }

        }

        static long popu[];
        static long happy[];
        static long count[]; // total people crossing that pos
        static long sum[]; // total sum of happy people including that.


        HashMap<Integer, ArrayList<Integer>>map= new HashMap<>();
        public static void bfs(int x,ArrayList<Long>curr){



        }


        public static void bfs1(int x){
            done[x]=true;
//            long total= popu[x];
            long smile= 0;
            ArrayList<Integer>nbrs= new ArrayList<>(vt.get(x).nb.keySet());
            for (int i = 0; i <nbrs.size() ; i++) {
                int r= nbrs.get(i);
                if(!done[r]){
                    bfs1(r);
//                    total+=count[r];
                    smile+=happy[r];
                }
            }
//            count[x]=total;
            sum[x]=smile;
        }


    }




    static class Reader {
        static BufferedReader reader;
        static StringTokenizer tokenizer;

        /**
         * call this method to initialize reader for InputStream
         */
        static void init(InputStream input) {
            reader = new BufferedReader(
                    new InputStreamReader(input));
            tokenizer = new StringTokenizer("");
        }

        /**
         * get next word
         */
        static String next() throws IOException {
            while (!tokenizer.hasMoreTokens()) {
                //TODO add check for eof if necessary
                tokenizer = new StringTokenizer(
                        reader.readLine());
            }
            return tokenizer.nextToken();
        }

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

        static double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

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


    static class Pair implements Comparable<Pair>     {
        int val;
        int pos;


        public Pair(int val, int pos) {
            this.pos = pos;
            this.val = val;

        }
        @Override
        public String toString() {
            return val + " " + pos;
        }

        @Override
        public int compareTo(Pair o) {
            if(this.pos >o.pos){
                return 1;
            }
            else if(this.pos==o.pos){

                return 0;
            }
            else{
                return -1;
            }
        }}



        static class Pair1 implements Comparable<Pair1>     {
            int val;
            int pos;


            public Pair1(int val, int pos) {
                this.pos = pos;
                this.val = val;

            }
            @Override
            public String toString() {
                return val + " " + pos;
            }

            @Override
            public int compareTo(Pair1 o) {
                if(this.val >o.val){
                    return 1;
                }
                else if(this.val==o.val){

                    return 0;
                }
                else{
                    return -1;
                }
            }
        }
    static ArrayList<Pair> findSubArrays(long[] arr, int n)
    {
        // create an empty map
        HashMap<Long,ArrayList<Integer>> map = new HashMap<>();

        // create an empty vector of pairs to store
        // subarray starting and ending index
        ArrayList<Pair> out = new ArrayList<>();

        // Maintains sum of elements so far
        long sum = 0;

        for (int i = 0; i < n; i++)
        {
            // add current element to sum
            sum += arr[i];

            // if sum is 0, we found a subarray starting
            // from index 0 and ending at index i
            if (sum == 0)
                out.add(new Pair(0, i));
            ArrayList<Integer> al = new ArrayList<>();

            // If sum already exists in the map there exists
            // at-least one subarray ending at index i with
            // 0 sum
            if (map.containsKey(sum))
            {
                // map[sum] stores starting index of all subarrays
                al = map.get(sum);
                for (int it = 0; it < al.size(); it++)
                {
                    out.add(new Pair(al.get(it) + 1, i));
                }
            }
            al.add(i);
            map.put(sum, al);
        }
        return out;
    }






    // After writing solution, quick scan for:
    //   array out of bounds
    //   special cases e.g. n=1?
    //
    // Big numbers arithmetic bugs:
    //   int overflow
    //   sorting, or taking max, or negative after MOD


    public static void main(String[] args)  throws IOException {
        Reader.init(System.in);
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        int t= Reader.nextInt();
        for (int tt = 0; tt <t ; tt++) {
            int n= Reader.nextInt();
            long arr[]= new long[n];
            long sum=0;
            for (int i = 0; i <n ; i++) {
                arr[i]= Reader.nextLong();
                if(i%2==0){
                    sum+=arr[i];
                }
            }
            ArrayList<Long>a1= new ArrayList<>();
            ArrayList<Long>a2= new ArrayList<>();
            for (int i = 0; i <n-1 ; i++) {
                if(i%2==0){
                    a1.add(arr[i+1]-arr[i]);
                }
                if(i%2==1){
                    a2.add(arr[i]-arr[i+1]);
                }
            }
//            System.out.println(a1);
//            System.out.println(a2);
            long sum1=0;
            long min=0;
            long max=0;
            for (int i = 0; i <a1.size() ; i++) {
                sum1+=a1.get(i);
                min= Math.min(min,sum1);
                max= Math.max(max,sum1-min);
            }

            long sum2=0;
            long min2=0;
            long max2=0;
            for (int i = 0; i <a2.size() ; i++) {
                sum2+=a2.get(i);
                min2= Math.min(min2,sum2);
                max2= Math.max(max2,sum2-min2);
            }
//            System.out.println(max+" "+max2);
            out.append((sum+Math.max(max,max2))+"\n");











        }

        out.flush();
        out.close();
        }





        public static boolean check(int arr[]){
        int sum=0;
        int n= arr.length;
            for (int i = 0; i <arr.length ; i++) {
                sum+=arr[i];
            }
            if(sum%2==1){
                return false;
            }

            else{
                sum/=2;
                boolean dp[][]= new boolean[n+1][sum+1]; // dp(i,j) will hopefully denote wheather making a sum of j is possible using the first i elements
                for (int i = 0; i <=n ; i++) {
                    dp[i][0]=true;
                }
                for (int i = 1; i <=n ; i++) {
                    for (int j = 0; j <=sum ; j++) {
                        if(arr[i-1]>j){
                            dp[i][j]=dp[i-1][j];
                        }
                        else{
                            dp[i][j]= dp[i-1][j] || dp[i-1][j-arr[i-1]];
                        }
                    }
                }
                return dp[n][sum];
            }

        }







    public static String convert(String s,int n){
        if(s.length()==n){
            return s;
        }
        else{
            int x= s.length();
            int v=n-x;
            String str="";
            StringBuilder s2= new StringBuilder();
            for (int i = 0; i <v ; i++) {
                s2.append('0');
            }
            StringBuilder s1= new StringBuilder(s);
            s2.append(s1);

//            str+=s;
            String q= s2.toString();
            return q;

        }
    }
    public static int lower(ArrayList<Integer>arr,int key){
        int low = 0;
        int high = arr.size()-1;
        while(low < high){
            int mid = low + (high - low)/2;
            if(arr.get(mid) >= key){
                high = mid;
            }
            else{
                low = mid+1;
            }
        }
        return low;
    }

    public static int upper(ArrayList<Integer>arr,int key){
        int low = 0;
        int high = arr.size()-1;
        while(low < high){
            int mid = low + (high - low+1)/2;
            if(arr.get(mid) <= key){
                low = mid;
            }
            else{
                high = mid-1;
            }
        }
        return low;
    }





    static long modExp(long a, long b, long mod) {
        //System.out.println("a is " + a + " and b is " + b);
        if (a==1) return 1;
        long ans = 1;
        while (b!=0) {
            if (b%2==1) {
                ans = (ans*a)%mod;
            }
            a = (a*a)%mod;
            b/=2;
        }
        return ans;
    }


    public static long modmul(long a, long b, long mod) {
        return b == 0 ? 0 : ((modmul(a, b >> 1, mod) << 1) % mod + a * (b & 1)) % mod;
    }

    static long sum(long n){
        //   System.out.println("lol="+ (n*(n-1))/2);
        return (n*(n+1))/2;
    }






    public static ArrayList<Integer> Sieve(int n) {
        boolean arr[]= new boolean [n+1];
        Arrays.fill(arr,true);
        arr[0]=false;
        arr[1]=false;
        for (int i = 2; i*i <=n ; i++) {
            if(arr[i]){
                for (int j = 2; j <=n/i ; j++) {
                    int u= i*j;
                    arr[u]=false;
                }}
        }
        ArrayList<Integer> ans= new ArrayList<>();
        for (int i = 0; i <n+1 ; i++) {
            if(arr[i]){
                ans.add(i);
            }
        }
        return ans;
    }




    static long power( long x, long y, long p)
    {

        long res = 1;


        x = x % p;

        if (x == 0) return 0;

        while (y > 0)
        {

            if((y & 1)==1)
                res = (res * x) % p;


            y = y >> 1;
            x = (x * x) % p;
        }
        return res;
    }

    public static long ceil_div(long a, long b){
        return (a+b-1)/b;
    }

    static long gcd(long a, long b)
    {
        if (a == 0)
            return b;
        return gcd(b % a, a);
    }

    static long lcm(long a, long b)
    {
        return (a*b)/gcd(a, b);
    }}

