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 getmax(nums):
	# print("getmax called",nums)
	if len(nums)==0:
		return 0,0,0
	if len(nums)==1:
		if nums[0]<0:
			return 0,0,0
		return nums[0],0,0
	meh=0
	msf=0
	start=0
	end=0
	s=0
	for i in range(len(nums)):
		meh=meh+nums[i]
		if meh<0:
			meh=0
			s=i+1
		if meh>msf:
			msf=meh
			start=s
			end=i
	
	
	return msf,start,end

t=int(input())
for test in range(t):
	n=int(input())
	a=list(map(int,input().split()))
	if n==1:
		print(a[0])
	else:

		nums=[]
		for i in range(0,n-1,2):
			nums.append(a[i+1]-a[i])
		
		nums2=[]
		for i in range(1,n-1,2):
			nums2.append(a[i]-a[i+1])


		# print(nums,nums2)
		m1,s1,e1=getmax(nums)
		m2,s2,e2=getmax(nums2)


		s1=2*s1
		e1=2*e1
		s2=1+2*s2
		e2=1+2*e2

		if m1>m2:
			start=s1
			end=e1
		else:
			start=s2
			end=e2
		
		# print("max found",max(m1,m2))
		# print("start,end",start,end)
		ans=0
		for i in range(0,n,2):
			ans+=a[i]
		# for i in range(end+1,n,2):
		# 	ans+=a[i]
		ans+=max(m1,m2)
		print(ans)




	






# s=input()
# res = 0
# init=0
# while(True):
#     cur = init
#     ok = True
#     print("\nwhile again",cur)
#     for i in range(len(s)):
#         res = res + 1
#         print("in loop,i,s[i],res",i,s[i],res)
#         if s[i] == '+':
#             cur = cur + 1
#         else:
#             cur = cur - 1
#         print("cur",cur)
#         if cur < 0:
#             ok = False
#             break
#     if ok:
#         break
#     init+=1



	

















	# ones=0
	# twos=0
	# zeros=1
	# claws=0
	# val=n
	# odd=0
	# count=0
	
	# m=1000000007
	# tval=0

	# even=0
	


	# while(val>1):

	# 	lz=zeros
	# 	lo=ones
	# 	lt=twos
	# 	zeros=lz+(2*lo)
	# 	ones=lz
	# 	twos=lo
	# 	claws=lo
		
	# 	clawvalue=((4%m)*(claws%m))%m
	# 	if count==0:
	# 		odd=((odd%m)+(clawvalue%m))%m
	# 	elif count==1:
	# 		even=((even%m)+(clawvalue%m))%m
	# 	else:
	# 		tval=((tval%m)+(clawvalue%m))%m

	# 	count+=1
	# 	count%=3
	# 	val-=1
	# print(even, odd, tval)

	# print(max(even,odd,tval))






		

	


	


	
	



	



		










	







	
