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 CP{
  public static OutputStream out=new BufferedOutputStream(System.out);
  static Scanner sc=new Scanner(System.in);
  static long mod=1000000007l;

  //nl-->neew line; //l-->line;  //arp-->array print;  //arpnl-->array print new line
  public static void nl(Object o) throws IOException{out.write((o+"\n").getBytes());}
  public static void l(Object o) throws IOException{out.write((o+"").getBytes());}
  public static void arp(int[] o) throws IOException{for(int i=0;i<o.length;i++) out.write((o[i]+" ").getBytes()); out.write(("\n").getBytes());}
  public static void arpnl(int[] o) throws IOException{for(int i=0;i<o.length;i++) out.write((o[i]+"\n").getBytes());}
  public static void scan(long[] a,int n) {for(int i=0;i<n;i++) a[i]=sc.nextLong();}
  public static void scan2D(int[][] a,int n,int m) {for(int i=0;i<n;i++) for(int j=0;j<m;j++) a[i][j]=sc.nextInt();}
  //
  static long cnt;
  static int[] dp;
  static TreeSet<Integer> ans;


  public static void main(String[] args) throws IOException{
    long sttm=System.currentTimeMillis();
    long mod=1000000007l;

    int t=sc.nextInt();
    while(t-->0){
        int n=sc.nextInt();
        long[] a=new long[n];
        scan(a,n);
        long[] psum=new long[n];
        psum[0]=a[0];if(n>1) psum[1]=a[1];
        for(int i=2;i<n;i++){
            psum[i]=psum[i-2]+a[i];
        }
        long[] dif=new long[n-1];
        for(int i=1;i<n;i++){
            if(i%2==1) dif[i-1]=a[i]-a[i-1];
            else dif[i-1]=a[i-1]-a[i];
        }
        long max_sum=0,max_end_here=0;
        for(int i=0;i<n-1;i+=2){
            max_end_here+=dif[i];
            if(max_end_here<0) max_end_here=0;
            if(max_sum<max_end_here) max_sum=max_end_here;
        }
        long max_sum2=0,max_end_here2=0;
        for(int i=1;i<n-1;i+=2){
            max_end_here2+=dif[i];
            if(max_end_here2<0) max_end_here2=0;
            if(max_sum2<max_end_here2) max_sum2=max_end_here2;
        }
        // nl(max_sum+" "+max_sum2+" "+Arrays.toString(psum));
        // nl(Arrays.toString(dif));
        long sum=Math.max(max_sum,max_sum2);
        if(n%2==0){
            nl((psum[n-2]+Math.max(0,sum)));
        }
        else{
            nl((psum[n-1]+Math.max(0,sum)));
        }
    }

    out.flush();
  }
}

class Pair{
  int st,nd;
  Pair(int st,int nd){
    this.st=st;
    this.nd=nd;
  }
}
