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 sys



def solve(arr):
    
    if len(arr) <= 1:
        return 0 if len(arr) == 0 else arr[0]

    max_sum = 0
    l = len(arr)
    #print(arr)
    # swapping range with two even indices --> no change in even sum
    # swapping range with two odd indices  --> no change in even sum
    evens = arr[0::2]
    odds  = arr[1::2]
    if l%2 == 1:
        odds.append(0) # both same length now

    #print('evens: ',evens)
    #print('odds: ',odds)
    
    hl = len(evens)

    even_cum = [arr[0]]*hl
    odd_cum = [arr[1]]*hl
    for ei in range(1,hl):
        even_cum[ei] = evens[ei] + even_cum[ei-1]
    for oi in range(1,hl):
        odd_cum[oi] = odds[oi] + odd_cum[oi-1]
    #print('even_cum:',even_cum)
    #print('odd_cum:',odd_cum)
    diff_r = [odds[i] - evens[i] for i in range(hl)]
    diff_l = [odds[i] - evens[i+1] for i in range(hl-1)]
    def largest_contig_sum( A ):
        n = len(A)
        #cum_sum = [A[0]]*n
        cum_sum = [0]*(n+1)
        big_diff = 0
        mn = 0
        for i in range(1,n+1):
            cum_sum[i] = cum_sum[i-1] + A[i-1]
            if cum_sum[i] < mn:
                mn = cum_sum[i] 
            elif cum_sum[i] - mn > big_diff:
                big_diff = cum_sum[i]-mn

        #print('  cum_sum:',cum_sum)
        return big_diff
    #print('RIGHT:', diff_r)
    #print('  largest right:', (largest_contig_sum(diff_r)))
    #print('LEFT:', diff_l)
    #print('  largest left:', (largest_contig_sum(diff_l)))
    return sum(evens) + max(largest_contig_sum(diff_r),largest_contig_sum(diff_l))
    


    # Consider all possible flips
    start = even_cum[-1]
    biggest_diff = 0
    for e1 in range(hl):
        for e2 in range(e1,hl): # want to include just 1 for 1
            if e1 == 0:
                etot = even_cum[e2]
                otot1 = odd_cum[e2]
                if otot1-etot > biggest_diff:
                    biggest_diff = otot1-etot
            else:
                etot = even_cum[e2]-even_cum[e1-1]
                otot1 = odd_cum[e2]-odd_cum[e1-1]
                if e1 == 1:
                    otot2 = odd_cum[e2-1]
                else:
                    otot2 = odd_cum[e2-1]-odd_cum[e1-2]
                biggest_diff = max(biggest_diff,otot1-etot,otot2-etot)
            '''
            #print(e1,e2)
            #single_fix = -1 if e1==e2 else 0
            etot = even_cum[e2] if e1 == 0 else even_cum[e2]-even_cum[e1-1]
            if True:#e1 > 0:
                otot1 = odd_cum[e2] if e1 == 0 else odd_cum[e2]-odd_cum[e1-1]
                #oelems = [odds[i] for i in range(e1,e2+1)]
                #print(e1,e2,'comparing {} to {} ({} to {})'.format(etot,otot1,[evens[i] for i in range(e1,e2+1)],oelems))

                #if otot1 > etot and b:
                #if start+otot1-etot > best:
                    #print(e1,e2,'  {} is better than {}'.format(start+otot1-etot,best))
                    #best = max(best,start+otot1-etot)
                best = max(best,start+otot1-etot)
            if e1 > 0:#e2 < hl:#(hl-1 if l%2 == 1 else hl):
            #if not e1==e2 and e1 > 0:#e2 < hl:#(hl-1 if l%2 == 1 else hl):
                otot2 = odd_cum[e2-1] if e1 == 1 else odd_cum[e2-1]-odd_cum[e1-2]
                #oelems = [odds[i] for i in range(e1-1,e2)]
                #print(e1,e2,'comparing {} to {} ({} to {})'.format(etot,otot2,[evens[i] for i in range(e1,e2+1)],oelems))
                #if otot2 > etot:
                #if start+otot2-etot > best:
                    #print(e1,e2,'  {} is better than {}'.format(start+otot2-etot,best))
                    #best = max(best,start+otot2-etot)
                best = max(best,start+otot2-etot)
            '''
    
    return start + biggest_diff



if __name__ == '__main__':
    IN = [x.strip() for x in sys.stdin.readlines()]

    T = int(IN[0])
    for ti in range(T):
        #n = for x in IN[1+2*ti].split(' ')]
        arr = [int(x) for x in IN[2+2*ti].split(' ')]
        #print( arr )
        max_sum = solve(arr)
        print(max_sum)

