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
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(list(s[:len(s) ]))
def invr():
    return(map(int,input().split()))

entries = inp()

for i in range(entries):
    n = inp()
    l = inlt()
    if(len(l) == 1 or len(l) == 2):
        print(max(l))
    else:
        two_string = []

        i = 0
        while(i < len(l)):
            if(i+1<len(l)):
                two_string.append(l[i+1]-l[i])
            i += 2
        #print(two_string)
        cur = -10000000
        max_val = -100000000
        cur_ind_start = 0
        ind_start = 0
        ind_end = 0

        for i in range(len(two_string)):
            x = two_string[i]
            if(x > cur + x):
                cur_ind_start = i
                cur = x
            else:
                cur += x
            if(cur > max_val):
                ind_start = cur_ind_start
                ind_end = i
                max_val = cur
            #print(x,cur, max_val)
        #print(ind_start,ind_end)
        two_string2 = []

        i = 1
        while(i < len(l)):
            if(i+1<len(l)):
                two_string2.append(l[i]-l[i+1])
            i += 2
        #print(two_string2)
        cur2 = -100000000
        max_val2 = -1000000000
        cur_ind_start2 = 0
        ind_start2 = -1
        ind_end2 = -1
        #print(two_string2)
        for i in range(len(two_string2)):
            x = two_string2[i]
            if(x > cur2 + x):
                cur_ind_start2 = i
                cur2 = x
            else:
                cur2 += x
            if(cur2 > max_val2):
                ind_start2 = cur_ind_start2
                ind_end2 = i
                max_val2 = cur2

        ind_start *= 2
        ind_end *=2
        ind_start2 *= 2
        ind_end2 *=2
        res = 0
        k = 0
        #print(max_val, max_val2)
        if(max_val <= 0 and max_val2 <= 0):
            while(k < len(l)):
                res += l[k]
                k += 2
        elif(max_val > max_val2):
            while(k < len(l)):
                if(k>=ind_start and k <= ind_end):
                    #print(l[k+1])
                    res += l[k+1]
                else:
                    #print(l[k])
                    res += l[k]
                k += 2
        else:
            k = 0
            while(k < len(l)):
                #print(ind_start2,ind_end2)
                if(k>=ind_start2+2 and k <= ind_end2+2):
                    #print(l[k-1])
                    res += l[k-1]
                else:
                    #print(l[k])
                    res += l[k]
                k += 2
        print(res)
