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.BufferedInputStream;
import java.lang.Math;
import java.math.BigDecimal;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
	// write your code here
        problem_1373D();
    }


    public static void problem_1() {
        int i=0,sum=0;
        while(i<1000) {
            if(i%3==0 || i%5==0){
                sum+=i;
            }
            ++i;
        }
        System.out.println(sum);
    }

    public static void problem_2() {
        int fib1=1,fib2=1,sum=0;
        int temp=0;
        while(fib2<4000000) {
            if(fib2%2==0)
                sum+=fib2;
            temp=fib2;
            fib2=fib1+fib2;
            fib1=temp;
        }
        System.out.println(sum);
    }

    public static void problem_3() {
        double i=2;
        double input=600851475143.0;
        double max=0,flag=0;
        double temp1=Math.sqrt(input),temp2=0.0;
        while(i<temp1) {
            if(input%i==0){
                 double j=2.0,temp3=0.0;
                 temp3=Math.sqrt(i);
                 while(j<temp3) {
                     if (i % j == 0) {
                         flag=1;
                         break;
                     }
                     ++j;
                 }
                 if(flag==0&&max<i)
                     max=i;
                 flag=0;
                 j=2.0;
                 temp2=input/i;
                 temp3=Math.sqrt(input/i);
                while(j<temp3) {
                    if (temp2 % j == 0) {
                        flag=1;
                        break;
                    }
                    ++j;
                }
                if(flag==0&&max<temp2)
                    max=temp2;
                flag=0;
            }
            ++i;
        }
        System.out.println(max);
    }

    public static void problem_4() {
        int i=100,j=100;
        int result=0;
        int temp1=0,temp2=0;
        while(i<1000) {
            while(j<1000) {
                temp1=i*j;
                temp2=0;
                if(temp1%10!=0) {
                    while(temp1>temp2) {
                        temp2=temp2*10+temp1%10;
                        temp1/=10;
                    }
                    if((temp1==temp2||temp1==temp2/10)&&result<i*j)
                        result=i*j;
                }
                ++j;
            }
            j=100;
            ++i;
        }
        System.out.println(result);
    }

    public static void problem_5() {
        int result=2521,flag=0;
        int[] a={11,13,14,15,16,17,18,19,20};
        while(result>2520) {
            for (int j : a) {
                if (result % j != 0) {
                    flag = 1;
                    break;
                }
            }
            if(flag==0) {
                System.out.println(result);
                break;
            }
            flag=0;
            ++result;
        }
    }

    public static void problem_6() {
        int sum1=0,sum2=0;
        for(int i=1;i<=100;++i) {
            sum1+=i*i;
            sum2+=i;
        }
        sum2*=sum2;
        System.out.println(sum2-sum1);
    }

    public static void problem_7() {
        int count=1,result=2;
        int flag=0;
        while(count<=10001) {
            for(int i=2;i<=Math.sqrt(result);++i) {
                if(result%i==0) {
                    flag=1;
                    break;
                }
            }
            if(flag==0) {
                System.out.println("第"+count+"个:"+result);
                count += 1;
            }
            ++result;
            flag=0;
        }
        System.out.println(result-1);
    }

    public static void problem_8() {
        String a = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
        double result=0,max=0;
        for(int i=0,j=13;i<a.length()&&j<a.length();++i,++j) {
            for(int k=i;k<j;++k) {
                max*=Integer.parseInt(String.valueOf(a.charAt(k)));
            }
            if(max>result) {
                result = max;
            }
            max=1;
        }
        BigDecimal bd = new BigDecimal(result);
        String str = bd.toPlainString();
        System.out.println(str);
    }

    public static void problem_9() {
        int result=0;
        for(int i=0;i<500;++i) {
            for(int j=0;j<250;++j) {
                int k=1000-i-j;
                if(i*i+j*j==k*k) {
                    result=i*j*k;
                    break;
                }
            }
            if(result!=0)
                break;
        }
        System.out.println(result);
    }

    public static void problem_10() {
        int[] a =new int[2000001];
        long result=0;
        for(int i=2;i<2000001;++i) {
            for(int j=2;j<=2000000/i;++j) {
                int k=i*j;
                if(k<=2000000)
                    a[k]=1;
            }
        }
        for(int n=2;n<2000001;++n) {
            if(a[n]!=1)
                result+=n;
        }
        System.out.println(result);
    }

    public static void problem_12() {
        int flag=0,count=0;
        int i=1,result=0;
        while(true) {
            result+=i;
            for(int j=1;j<=Math.sqrt(result);++j) {
                if(result%j==0) {
                    if(j==Math.sqrt(result))
                        ++count;
                    else
                        count+=2;
                }
            }
            ++i;
            if(count>=500)
                break;
            count=0;
        }
        System.out.println(result);
    }

    public static void problem_14() {
        long result=0,count=1,maxcount=0;
        long num;
        long[] a=new long[1000001];
        for(int i=1;i<1000000;++i) {
            num=i;
            while(num!=1) {
                if(num%2==0)
                    num/=2;
                else
                    num=3*num+1;
                if(num<i){
                    count+=a[(int)num];
                    num=1;
                }
                else
                    ++count;
            }
            a[i]=count;
            if(maxcount<count)
            {
                result=i;
                maxcount=count;
            }
            count=1;
        }
        System.out.println(result+":"+maxcount);
    }

    public static void problem_1007() {
        Scanner input = new Scanner(System.in);
        int first_num = input.nextInt();
        int second_num = input.nextInt();
        int number = input.nextInt();
        int f_n_1=1,f_n_2=1;
        int result=0;
        while (first_num != 0) {
            for(int i=3;i<=number;++i){
                result=(first_num*f_n_1+second_num*f_n_2)%7;
                f_n_2=f_n_1;
                f_n_1=result;
            }
            System.out.println(result);
            first_num = input.nextInt();
            second_num = input.nextInt();
            number = input.nextInt();
            f_n_1=1;
            f_n_2=1;
            if(first_num==0)
                System.out.print("\n");
        }
    }

    public static void problem_1000() {
        Scanner input = new Scanner(System.in);
        int first_num = input.nextInt();
        int second_num = input.nextInt();
        System.out.println(first_num+second_num);
    }

    public static void problem_1373D() {
        Scanner input=new Scanner(System.in);
        for(int t=input.nextInt();t>0;t--) {
            int n=input.nextInt();
            long arr[]=new long [n+1];
            long ans=0;
            long a=0,b=0,max=0;
            for(int i=1;i<=n;i++) {
                arr[i]=input.nextLong();
                if(i%2==1)ans+=arr[i];
            }
            for(int i=2;i<=n;i+=2) {
                a=Math.max(0, arr[i]-arr[i-1]+a);
                max=Math.max(max,a);
            }
            for(int i=3;i<=n;i+=2) {
                b=Math.max(0, arr[i-1]-arr[i]+b);
                max=Math.max(max, b);
            }
            System.out.println(ans+max);
        }
    }
}