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
t=int(input())
while t>0:
	t-=1
	n=int(input())	
	li=list(map(int,input().split()))
	if n>2:
		#li=list(map(int,input().split()))
		a=[]
		b=[]
		k=int(n/2)
		x=k
		y=k
		i=0
		j=1
		while x>0:
			z=li[i+1]-li[i]
			a.append(z)
			i+=2
			x-=1
		if n%2==0:
			while y>1:
				z=li[j]-li[j+1]
				b.append(z)
				j+=2
				y-=1
		else:
			while y>0:
				z=li[j]-li[j+1]
				b.append(z)
				j+=2
				y-=1
		for i in range(1,len(a)):
			a[i]=max(a[i],a[i-1]+a[i])
		for i in range(1,len(b)):
			b[i]=max(b[i],b[i-1]+b[i])
		sum=0
		for i in range(len(li)):
			if i%2==0:
				sum+=li[i]
		q=max(a)
		r=max(b)
		w=max(q,r)
		if w>0:
			sum=sum+w
		print(sum)
	elif n==1:
		print(li[0])
	elif n==2:
		print(max(li[0],li[1]))





