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
#missing a whole damn case

def input():
	return sys.stdin.readline().rstrip()

def input_split():
	return [int(i) for i in input().split()]

testCases = int(input())
answers = []


def best_subarray(array):
	m = len(array)
	best_including_last_using_first_i_elems = [0]
	for i in range(m):
		option1 = (array[i] + best_including_last_using_first_i_elems[-1])
		option2 = (array[i])
		choice = max(option1, option2)
		final = max(0, choice)
		best_including_last_using_first_i_elems.append(final)
	return max(best_including_last_using_first_i_elems)


for _ in range(testCases):
	#take input
	n = int(input())
	arr = input_split()
	# untouchable = 0
	# if n%2 == 1:
		# arr = arr[:-1]
		# n = n - 1

	if n%2 == 0:
		diff = [arr[2*i+1] - arr[2*i] for i in range(n//2)]
		diff2 = [arr[2*i+1] - arr[2*i+2] for i in range(n//2 - 1)]
	else:
		diff = [arr[2*i+1] - arr[2*i] for i in range(n//2)]
		diff2 = [arr[2*i+1] - arr[2*i+2] for i in range((n//2))]
	# diff = [odd_ind[i] - even_ind[i] for i in range(n//2)]
	# diff2 = [odd_ind[i] - even_ind[i+1] for i in range(n//2 - 1)]
	# del odd_ind
	# del even_ind
	even_ind = [arr[i] for i in range(n) if i%2 == 0]
	odd_ind = [arr[i] for i in range(n) if i%2 == 1]
	temp = sum(even_ind)
	ans = temp + max(best_subarray(diff), best_subarray(diff2))

	#find max cont subarray for diff
	# maxi = 0 #dont take anythning 
	# left = 0
	# right = 0 #from left to right -1
	# m = n//2
	# best_till_now = 0
	# l, r = 0,0
	# best_left, best_right = 0, -1
	# best_including_last_using_first_i_elems = [0]
	# for i in range(m):
	# 	option1 = (diff[i] + best_including_last_using_first_i_elems[-1])
	# 	option2 = (diff[i])
	# 	# if option1 > 0:
	# 	choice = max(option1, option2)
	# 	if option2 > option1:
	# 		l, r = i, i #inclusive
	# 	else:
	# 		r = i
	# 	final = max(0, choice)
	# 	best_including_last_using_first_i_elems.append(final)
	# 	if final > best_till_now:
	# 		best_left, best_right = l, r
	# 		best_till_now = final
	# 	# if choice == 0:
	# 	# 	pass
	# 	# else:
	# 	# 	if choice > curr_max:

	# # ans1 = sum(even_ind[:best_left] + even_ind[best_right+1:] + odd_ind[best_left:best_right+1])
	




	# ans2 = sum(even_ind[:best_left+1] + even_ind[best_right+2:] + odd_ind[best_left:best_right+1])
	# ans = max(ans1, ans2)
	# while(True):
	# 	if (right <= left):
	# 		right += 1
	# 	# if()
	# 	else:
	# 		if right >= m:
	# 			break #check later



	answers.append(ans)

print(*answers, sep = '\n')
