Given an array $a$ consisting of $n$ elements, find the maximum possible sum the array can have after performing the following operation any number of times:

Choose $2$ adjacent elements and flip both of their signs. In other words choose an index $i$ such that $1 \leq i \leq n - 1$ and assign $a_i = -a_i$ and $a_{i+1} = -a_{i+1}$.


-----Input-----

The input consists of multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. The descriptions of the test cases follow.

The first line of each test case contains an integer $n$ ($2 \leq n \leq 2\cdot10^5$) — the length of the array.

The following line contains $n$ space-separated integers $a_1,a_2,\dots,a_n$ ($-10^9 \leq a_i \leq 10^9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot10^5$.


-----Output-----

For each test case, output the maximum possible sum the array can have after performing the described operation any number of times.


-----Examples-----

Input
5
3
-1 -1 -1
5
1 5 -5 0 2
3
1 2 3
6
-1 10 9 8 7 6
2
-1 -1
Output
1
13
6
39
2


-----Note-----

For the first test case, by performing the operation on the first two elements, we can change the array from $[-1, -1, -1]$ to $[1, 1, -1]$, and it can be proven this array obtains the maximum possible sum which is $1 + 1 + (-1) = 1$.

For the second test case, by performing the operation on $-5$ and $0$, we change the array from $[1, 5, -5, 0, 2]$ to $[1, 5, -(-5), -0, 2] = [1, 5, 5, 0, 2]$, which has the maximum sum since all elements are non-negative. So, the answer is $1 + 5 + 5 + 0 + 2 = 13$.

For the third test case, the array already contains only positive numbers, so performing operations is unnecessary. The answer is just the sum of the whole array, which is $1 + 2 + 3 = 6$.

Source: codeforces | Difficulty: EASY
Tags: Dynamic programming

Sorting

Greedy algorithms


Solutions:
for s in [*open(0)][2::2]:
	a = list(map(abs, map(int, s.split())))
	print(sum(a) - s.count('-') % 2 * 2 * min(a))


for k in [*open(0)][2::2]:
	a = (*map(abs, map(int, k.split())),)
	print(sum(a) - k.count('-') % 2 * 2 * min(a))


for _ in range(int(input())):
	input()
	s = input()
	a = list(map(abs, map(int, s.split())))
	print(sum(a) - 2 * (s.count('-') % 2) * min(a))


import sys

def solve(n, array):
	absarray = [abs(i) for i in array]
	fn = 0
	for ar in array:
		if ar < 0:
			fn += 1
	if not fn % 2:
		return sum(absarray)
	return sum(absarray) - 2 * min(absarray)

def main():
	t = int(input())
	for i in range(t):
		n = int(sys.stdin.readline())
		array = list(map(int, sys.stdin.readline().split()))
		print(solve(n, array))
main()


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans1 = list(map(abs, arr))
	ans2 = sum((1 for i in arr if i < 0))
	if ans2 % 2 == 0:
		print(sum(ans1))
	else:
		result = min(ans1)
		print(sum(ans1) - 2 * result)


import sys

def solve(length_, line):
	ii = line.count('-')
	line = line.split()
	val_ = list(map(abs, map(int, line)))
	if int(str(ii)[-1]) % 2 == 1:
		return sum(val_) - 2 * min(val_)
	else:
		return sum(val_)

def main():
	test_num = 0
	line = sys.stdin.readline().rstrip()
	tot_tests = int(line)
	while test_num < tot_tests:
		line = sys.stdin.readline().rstrip()
		length_ = int(line)
		line = sys.stdin.readline().rstrip()
		result_ = solve(length_, line)
		sys.stdout.write(str(result_) + '\n')
		test_num += 1
main()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = sum((x < 0 for x in a))
	a = list(map(abs, a))
	s = sum(a)
	if c & 1:
		s -= 2 * min(a)
	print(s)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	negative = sum((x < 0 for x in arr))
	sm = sum(map(abs, arr))
	if negative % 2:
		print(sm - min(map(abs, arr)) * 2)
	else:
		print(sm)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	total = sum(map(abs, a))
	num_negative = 0
	for num in a:
		if num < 0:
			num_negative += 1
	if num_negative % 2 == 1:
		total -= 2 * min(map(abs, a))
	print(total)


t = int(input())
resp = ''
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr_plus = list(map(abs, arr))
	cntr = 0
	for j in arr:
		if j < 0:
			cntr += 1
	resp += f'{sum(arr_plus) - 2 * (0 if cntr % 2 == 0 else min(arr_plus))}\n'
print(resp)


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	cnt = 0
	for i in a:
		cnt += i < 0
	b = list(map(abs, a))
	print(sum(b) - 2 * min(b) * (cnt % 2))
for i in range(int(input())):
	solve()


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split(' ')))
	k = [abs(x) for x in l]
	cnt = 0
	for j in l:
		if j < 0:
			cnt += 1
	if cnt % 2 == 0:
		print(sum(k))
	else:
		print(sum(k) - 2 * min(k))


def start():
	n = int(input())
	arr = list(map(int, input().split()))
	ans1 = sum(map(abs, arr))
	ans2 = sum([1 for x in arr if x < 0])
	if ans2 % 2 == 0:
		print(ans1)
		return
	res = min(map(abs, arr))
	print(ans1 - 2 * res)
t = int(input())
while t != 0:
	t -= 1
	start()


import sys

def answer():
	pass

def solution():
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	m = 1000000000000
	s = 0
	for i in a:
		if abs(i) < m:
			m = abs(i)
		if i < 0:
			c += 1
		s += abs(i)
	if c % 2 == 0:
		print(s)
	else:
		print(s - m * 2)
t = int(input())
for _ in range(t):
	solution()


for t in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	count = 0
	for i in range(n):
		if l1[i] < 0:
			l1[i] = -l1[i]
			count += 1
	if count % 2 == 0:
		print(sum(l1))
	else:
		print(sum(l1) - 2 * min(l1))


def main():
	test_cases = int(input().strip())
	for _ in range(test_cases):
		n = int(input().strip())
		a = list(map(int, input().strip().split()))
		t = 0
		s = []
		for i in a:
			s.append(abs(i))
			if i <= 0:
				t += 1
		result = sum(s)
		if t % 2 != 0:
			result -= min(s) * 2
		print(result)
main()


def operation(lista, n):
	neg = 0
	for i in range(n):
		if lista[i] < 0:
			neg += 1
	suma = sum(map(abs, lista))
	if neg % 2 == 0:
		return suma
	lista = map(abs, lista)
	return suma - 2 * min(lista)
cases = int(input())
for i in range(cases):
	n = int(input())
	num = list(map(int, input().split()))
	print(operation(num, n))


def solve():
	t = 1
	t = int(input())
	while t:
		t -= 1
		n = int(input())
		a = [int(x) for x in input().split()]
		ngc = 0
		for i in range(n):
			if a[i] < 0:
				a[i] = abs(a[i])
				ngc += 1
		maxi = sum(a)
		print(maxi - 2 * min(a) if ngc % 2 else maxi)
solve()


def solve():
	t = int(input())
	while t != 0:
		n = int(input())
		cnt = 0
		ans = 0
		mn = 999999999999999999
		num = list(map(int, input().split()))
		for a in num:
			if a < 0:
				cnt += 1
				ans += abs(a)
				if abs(a) < mn:
					mn = abs(a)
			else:
				ans += a
				if a < mn:
					mn = a
		if cnt % 2 == 0:
			print(ans)
		else:
			print(ans - 2 * mn)
		t -= 1
solve()


def solve():
	n = int(input())
	l = list(map(int, input().split()))
	m = list(map(lambda x: abs(x), l))
	negative = sum((1 for i in l if i < 0))
	if negative % 2:
		print(sum(m) - min(m) * 2)
	else:
		print(sum(m))
for _ in range(int(input())):
	solve()


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	k = 0
	for el in a:
		if el < 0:
			k += 1
	if k % 2 == 0:
		print(sum(list(map(abs, a))))
	else:
		print(sum(list(map(abs, a))) - 2 * min(list(map(abs, a))))


t = int(input())
ans = []
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	(c1, c2) = (0, 0)
	for i in a:
		if i < 0:
			c1 += 1
		elif i == 0:
			c2 += 1
	a = list(map(abs, a))
	if c1 % 2 != 0 and c2 == 0:
		res = sum(a) - 2 * min(a)
	else:
		res = sum(a)
	ans.append(res)
for _ in ans:
	print(_)


def fun(a, t):
	odd_count = 0
	temp = [abs(ii) for ii in t]
	for _ in t:
		if _ < 0:
			odd_count += 1
	if odd_count % 2 == 0:
		return sum(temp)
	return sum(temp) - 2 * min(temp)
for _ in range(int(input())):
	a = int(input())
	t = [int(i) for i in input().split()]
	print(fun(a, t))


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	absed_a = list(map(abs, a))
	count = 0
	for el in a:
		if el < 1:
			count = count + 1
	if count % 2 == 0:
		print(sum(absed_a))
	else:
		print(sum(absed_a) - 2 * min(absed_a))


for nnm in range(int(input(''))):
	n = int(input(''))
	k = [int(x) for x in input('').split(' ')]
	l = [abs(x) for x in k]
	if n == 2:
		print(max(sum(k), -sum(k)))
	else:
		neg = sum([1 if x < 0 else 0 for x in k])
		if neg % 2 == 1:
			print(sum(l) - 2 * min(l))
		else:
			print(sum(l))


def solve():
	n = int(input())
	lst = list(map(int, input().split()))
	negs = 0
	for i in range(n):
		if lst[i] < 0:
			negs += 1
	if negs % 2 == 0:
		print(sum((abs(x) for x in lst)))
	else:
		print(sum((abs(x) for x in lst)) - 2 * min((abs(x) for x in lst)))
t = int(input())
for _ in range(t):
	solve()


for i in range(int(input())):
	b = int(input())
	c = list(map(int, input().split()))
	d = abs(c[0])
	m = 0
	k = 0
	m1 = 0
	for i in c:
		if i < 0:
			i = -i
			k += 1
		m += i
		if i < d:
			d = i
	if k % 2 == 1:
		print(m - d * 2)
	else:
		print(m)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	temp = [abs(i) for i in arr]
	tot = sum(temp)
	totneg = len([i for i in arr if i < 0])
	if not totneg % 2:
		print(tot)
		continue
	min_ = min(temp)
	print(tot - 2 * min_)


a = int(input())
for _ in range(a):
	c = int(input())
	b = list(map(int, input().split()))
	e = 0
	gt = 0
	for i in b:
		if i <= 0:
			gt += 1
	b = list(map(lambda x: abs(x), b))
	if gt % 2 == 0:
		print(sum(b))
	else:
		print(sum(b) - 2 * min(b))


num = int(input())
_ = 0
x = []
y = []
while _ < num:
	y.append(int(input()))
	x.append(list(map(int, input().split())))
	_ += 1
for i in range(num):
	n = x[i]
	m = y[i]
	count = 0
	for t in n:
		if t < 0:
			count += 1
	if count % 2 == 0:
		n = list(map(abs, n))
		print(sum(n))
	elif count % 2 != 0:
		n = list(map(abs, n))
		print(sum(n) - 2 * min(n))


cases = int(input())
for _ in range(cases):
	N = int(input())
	nums = list(map(int, input().split()))
	pos = []
	neg = []
	smallest = 100000000000.0
	for i in nums:
		if abs(i) < smallest:
			smallest = abs(i)
		if i > 0:
			pos.append(i)
		else:
			neg.append(i * -1)
	if len(neg) % 2 == 0:
		print(sum(pos) + sum(neg))
	else:
		print(sum(pos) + sum(neg) - smallest * 2)


for _ in range(int(input())):
	n = int(input())
	num = list(map(int, input().split()))
	cnt = 0
	for i in range(n):
		if num[i] < 0:
			cnt += 1
			num[i] = -num[i]
	if cnt % 2 == 0:
		print(sum(num))
	else:
		print(sum(num) - 2 * min(num))


tc = int(input())
for _ in range(tc):
	n = int(input())
	a = list(map(int, input().split()))
	neg = []
	for i in a:
		if i <= 0:
			neg.append(i)
	sp = 10 ** 10
	for i in a:
		if i > 0:
			if sp > i:
				sp = i
	if len(neg) % 2 == 0:
		print(sum(a) - 2 * sum(neg))
	else:
		if abs(sorted(neg)[-1]) < sp:
			sp = abs(sorted(neg)[-1])
		print(sum(a) - 2 * sum(neg) - 2 * sp)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	neg = 0
	for i in range(n):
		if l[i] < 0:
			neg += 1
			l[i] = -l[i]
	if neg & 1:
		print(sum(l) - 2 * min(l))
	else:
		print(sum(l))


for _ in range(int(input().strip())):
	n = int(input().strip())
	a = list(map(int, input().split()))
	print(sum((abs(x) for x in a)) - (sum((x <= 0 for x in a)) & 1) * 2 * min((abs(x) for x in a)))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	absa = list(map(abs, a))
	negs = sum([1 for i in a if i <= 0])
	ans = sum(absa) if negs % 2 == 0 else sum(absa) - 2 * min(absa)
	print(ans)


import sys
input = sys.stdin.readline

def main():
	t = int(input().strip())
	for _ in range(t):
		n = int(input().strip())
		a = [int(x) for x in input().strip().split()]
		negs = 0
		sum = 0
		for i in range(n):
			if a[i] < 0:
				negs += 1
				a[i] = -a[i]
			sum += a[i]
		if negs % 2 == 1:
			sum -= 2 * min(a)
		print(sum)
main()


def solve(n, arr):
	negcount = sum([i < 0 for i in arr])
	arr = [abs(i) for i in arr]
	if negcount & 1:
		return sum(arr) - (min(arr) << 1)
	return sum(arr)
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(solve(n, arr))


import os
import math
import collections
import bisect
import functools
import itertools
import heapq

def solve(a, n):
	neg = len([x for x in a if x < 0])
	a = [abs(x) for x in a]
	if neg % 2 == 0:
		return sum(a)
	return sum(a) - 2 * min(a)
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(solve(a, n))


t = int(input())
for test_case in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	negative_count = 0
	for i in range(n):
		if arr[i] < 0:
			negative_count += 1
			arr[i] *= -1
	minimum = min(arr)
	if negative_count % 2 == 0:
		print(sum(arr))
	else:
		print(sum(arr) - minimum - minimum)


for i in range(int(input())):
	num = int(input())
	n = list(map(int, input().strip().split()))
	sumy = sum((1 for i in n if i < 0))
	newlist = [abs(i) for i in n]
	miny = min(newlist)
	if sumy % 2 == 1:
		print(sum(newlist) - miny - miny)
	else:
		print(sum(newlist))


n = int(input())
for _ in range(n):
	n1 = int(input())
	li = list(map(int, input().split()))
	cn = 0
	for i in range(len(li)):
		if li[i] < 0:
			cn += 1
			li[i] = -li[i]
	if cn % 2 == 0:
		s = sum(li)
		print(s)
	else:
		s = sum(li) - 2 * min(li)
		print(s)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	t = 0
	s = []
	for i in a:
		s.append(abs(i))
		if i <= 0:
			t += 1
	if t % 2 == 0:
		print(sum(s))
	else:
		print(sum(s) - min(s) * 2)


for _ in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	a = [abs(x) for x in l]
	ne = 0
	ans = 0
	e = 0
	for ele in l:
		if ele < 0:
			e += 1
	if a == l:
		ans = sum(l)
	elif e % 2 == 0:
		ans = sum(a)
	else:
		ans = sum(a) - 2 * abs(min(a))
	print(ans)


def solve():
	num_elements = int(input().strip())
	values = [int(x) for x in input().strip().split()]
	sum_of_values = 0
	num_negative = 0
	for value in values:
		sum_of_values += abs(value)
		if value < 0:
			num_negative += 1
	for (i, value) in enumerate(values):
		if value < 0:
			values[i] = abs(value)
	if num_negative % 2 == 0:
		print(sum_of_values)
		return
	min_value = min(values)
	print(sum_of_values - 2 * min_value)
num_tests = int(input().strip())
for _ in range(num_tests):
	solve()


t = int(input())
for _ in range(0, t):
	n = int(input())
	list1 = [int(num) for num in input().split()]
	negs = 0
	for i in range(0, n):
		if list1[i] < 0:
			negs += 1
			list1[i] = list1[i] * -1
	if negs % 2 == 0:
		print(sum(list1))
	else:
		print(sum(list1) - 2 * min(list1))


t = int(input())
for _ in range(t):
	n = int(input())
	x = list(map(int, input().split(' ')))
	res = 0
	z = 0
	for i in x:
		if i < 0:
			z += 1
	if z == 0:
		print(sum(x))
	elif z % 2 == 0:
		for i in x:
			res += abs(i)
		print(res)
	else:
		if 0 in x:
			m = [abs(i) for i in x]
			res = sum(m)
		else:
			m = [abs(i) for i in x]
			v = min(m)
			res = sum(m) - min(m) - min(m)
		print(res)


import sys, math, bisect, collections, itertools, heapq
from collections import defaultdict, deque
sys.setrecursionlimit(50000)
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	l = list(map(int, sys.stdin.readline().split()))
	count = 0
	for i in range(n):
		if l[i] < 0:
			count += 1
			l[i] *= -1
	if count % 2 == 0:
		print(sum(l))
	else:
		print(sum(l) - 2 * min(l))


for i in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	count = 0
	x = []
	for i in s:
		if i < 0:
			count += 1
			x.append(abs(i))
		else:
			x.append(i)
	if count % 2 == 0:
		print(sum(x))
	else:
		print(sum(x) - 2 * min(x))


from collections import defaultdict
tests = int(input())
for _ in range(tests):
	lgth = int(input()) - 1
	numbers = list(map(int, input().split()))
	zero = False
	_ve = 0
	for n in numbers:
		if n == 0:
			zero = True
			break
		if n < 0:
			_ve += 1
	numbers = list(map(abs, numbers))
	if zero or _ve % 2 == 0:
		print(sum(numbers))
	else:
		print(sum(numbers) - 2 * min(numbers))


t = int(input())
for _ in range(t):
	l = int(input())
	list1 = list(map(int, input().split()))
	num = 0
	minn = abs(max(list1))
	for i in list1:
		if i <= 0:
			num += 1
		if abs(i) < minn:
			minn = abs(i)
	ans = 0
	if num & 1 == 0:
		ans = sum(map(abs, list1))
	else:
		ans = sum(map(abs, list1)) - minn * 2
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	num = 0
	for i in l:
		if i < 0:
			num += 1
	if num % 2 == 0:
		print(sum((abs(x) for x in l)))
	else:
		print(sum((abs(x) for x in l)) - 2 * min((abs(x) for x in l)))


def max_sum(n, arr):
	count_neg = 0
	sum = 0
	is_zero = False
	greatest_neg = 9999999999
	for i in range(n):
		if arr[i] < 0:
			sum = sum - arr[i]
			count_neg += 1
		elif arr[i] > 0:
			sum += arr[i]
		elif arr[i] == 0:
			is_zero = True
		if abs(arr[i]) < greatest_neg:
			greatest_neg = abs(arr[i])
	if count_neg % 2 == 1 and is_zero == False:
		print(sum - 2 * greatest_neg)
	else:
		print(sum)

def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().split()))
		max_sum(n, arr)
main()


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	dem = 0
	sum = 0
	for i in range(len(a)):
		if a[i] < 0:
			dem += 1
			a[i] = -a[i]
		sum = sum + a[i]
	if dem % 2 == 0:
		print(sum)
	else:
		print(sum - min(a) * 2)


n = int(input())
for i in range(n):
	l = int(input())
	s = [int(i) for i in input().split()]
	n = 0
	for i in s:
		if i <= 0:
			n += 1
	sa = list(map(abs, s))
	if n % 2 == 0:
		print(sum(sa))
	else:
		print(sum(sa) - min(sa) * 2)


for t in range(int(input())):
	(n, a) = (int(input()), [int(x) for x in input().split()])
	negcnt = 0
	for i in range(n):
		if a[i] < 0:
			negcnt += 1
			a[i] = -a[i]
	if negcnt % 2 == 0:
		print(sum(a))
	else:
		print(sum(a) - 2 * min(a))


import sys
t = int(sys.stdin.readline())
for i in range(t):
	n = int(sys.stdin.readline())
	lst = list(map(int, sys.stdin.readline().split()))
	ele = 0
	for j in lst:
		if j < 0:
			ele += 1
	arr = []
	for j in lst:
		arr.append(abs(j))
	if ele % 2 == 0:
		print(sum(arr))
	else:
		mi = min(arr)
		s = sum(arr)
		print(s - 2 * mi)


out = []
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	cntm = 0
	for i in a:
		if i <= 0:
			cntm += 1
	a1 = [abs(i) for i in a]
	if cntm % 2 == 0:
		out.append(sum(a1))
	else:
		out.append(sum(a1) - min(a1) * 2)
for i in out:
	print(i)


t = int(input())
res = []

def max_sum_flip(a):
	n = len(a)
	total_sum = 0
	num_of_negatives = 0
	for i in range(n):
		if a[i] < 0:
			num_of_negatives += 1
			a[i] = -a[i]
		total_sum += a[i]
	if num_of_negatives % 2 == 0:
		return total_sum
	else:
		return total_sum - 2 * min(a)
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	res.append(max_sum_flip(a))
for i in res:
	print(i)


import sys, math, cmath, time
from bisect import bisect_left
start_time = time.time()

def solve():
	n = inp()
	l = [int(k) for k in inps()]
	a = []
	c = 0
	for i in l:
		a.append(abs(i))
		if i < 0:
			c += 1
	if c % 2 == 0:
		print(sum(a))
		return
	else:
		print(sum(a) - 2 * min(a))

def main():
	testcases = 1
	testcases = inp()
	for each_testcase in range(testcases):
		solve()

def inp():
	return int(input())

def inps():
	return input().split()
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
	input = sys.stdin.readline
main()


import sys
n = int(next(sys.stdin))
for i in range(n):
	next(sys.stdin)
	arr = next(sys.stdin).strip().split(' ')
	arr = list((int(j) for j in arr))
	m = 10 ** 9
	c = 0
	s = 0
	for j in arr:
		if abs(j) < m:
			m = abs(j)
		if j < 0:
			c += 1
		s += abs(j)
	print(s - c % 2 * m * 2)


def setlen(s):
	return len(set(s))
t = int(input())
for _ in range(t):
	n = int(input())
	minus = 0
	inp = list(map(int, input().split()))
	for i in range(n):
		if inp[i] < 0:
			minus += 1
			inp[i] = -inp[i]
	res = sum(inp)
	if minus % 2 == 1:
		res -= 2 * min(inp)
	print(res)


import sys
from collections import deque
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
n = inp()
for _ in range(n):
	m = inp()
	array = inlt()
	sm = sum(array)
	pos = []
	neg = []
	for i in array:
		if i >= 0:
			pos.append(i)
		else:
			neg.append(i)
	answer = sm
	if len(array) == len(pos):
		answer = sm
	elif len(neg) % 2 == 0:
		answer = sm + 2 * -1 * sum(neg)
	else:
		neg_max = max(neg)
		neg_sum = sum(neg)
		pos_sum = sum(pos)
		if not pos:
			answer = -sm + 2 * neg_max
		else:
			pos_min = min(pos)
			answer = sm - (neg_sum - neg_max) * 2
			if pos_min < abs(neg_max):
				answer -= pos_min * 2
				answer -= neg_max * 2
	print(answer)


def solve(arr):
	num_of_neg = 0
	for i in range(len(arr)):
		if arr[i] < 0:
			num_of_neg += 1
			arr[i] *= -1
	s = sum(arr)
	if not num_of_neg % 2:
		return s
	else:
		return s - 2 * min(arr)
n = int(input())
for _ in range(n):
	l = int(input())
	arr = [int(_) for _ in input().split()]
	print(solve(arr))


t = int(input())
for i in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	c = 0
	for k in range(n):
		if s[k] < 0:
			c += 1
			s[k] = abs(s[k])
	if c % 2 == 0:
		total = sum(s)
	if c % 2 == 1:
		total = sum(s) - 2 * min(s)
	print(total)


import sys
input = sys.stdin.readline
tests = int(input())
for test in range(tests):
	n = int(input())
	a = list(map(int, input().split()))
	even_negatives = True
	minimum = abs(a[0])
	summan = 0
	for integ in a:
		if abs(integ) < minimum:
			minimum = abs(integ)
		if integ < 0:
			even_negatives = not even_negatives
			summan -= integ
		else:
			summan += integ
	if even_negatives:
		print(summan)
	else:
		print(summan - 2 * minimum)


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	minus_count = 0
	for i in a:
		if i < 0:
			minus_count += 1
	if minus_count % 2 == 0:
		print(sum([i if i >= 0 else -i for i in a]))
	else:
		amin = min([abs(i) for i in a])
		print(sum([i if i >= 0 else -i for i in a]) - 2 * amin)


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	zero = 0 in lst
	neg = sum((int(x < 0) for x in lst))
	if neg % 2 == 0:
		print(sum((abs(x) for x in lst)))
	elif zero:
		print(sum((abs(x) for x in lst)))
	else:
		Min = float('inf')
		for x in lst:
			if abs(x) < Min:
				Min = abs(x)
		print(sum((abs(x) for x in lst)) - 2 * Min)


for _ in range(int(input())):
	ln = int(input())
	ls = list(map(int, input().split()))
	nc = 0
	ab = []
	for i in ls:
		if i < 0:
			nc += 1
		ab.append(abs(i))
	if nc % 2 == 0:
		print(sum(ab))
	elif 0 in ab:
		print(sum(ab))
	else:
		print(sum(ab) - 2 * min(ab))


ri = lambda : int(input())
rl = lambda : list(map(int, input().split()))
rs = lambda : input()

def solve():
	n = ri()
	a = rl()
	neg = total = 0
	_min = float('inf')
	for num in a:
		if num < 0:
			neg += 1
		total += abs(num)
		_min = min(_min, abs(num))
	if neg & 1:
		total -= _min * 2
	return total

def main():
	for _ in range(ri()):
		print(solve())
main()


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	negatives = 0
	zeroes = False
	for i in range(n):
		if arr[i] < 0:
			negatives += 1
			arr[i] = abs(arr[i])
		if arr[i] == 0:
			zeroes = True
	sum_ = sum(arr)
	if negatives % 2 == 0 or zeroes == True:
		print(sum_)
	else:
		print(sum_ - 2 * min(arr))


import sys
input = sys.stdin.readline
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	negatives = 0
	zeros = 0
	sumofelements = 0
	for i in a:
		if i > 0:
			sumofelements += i
		else:
			sumofelements -= i
		if i < 0:
			negatives += 1
		if i == 0:
			zeros += 1
	min = 10000000000
	for i in a:
		if i > 0:
			if i < min:
				min = i
		elif -i < min:
			min = -i
	if negatives % 2 == 0 or zeros > 0:
		print(sumofelements)
	else:
		print(sumofelements - 2 * min)


t = int(input())
for i in range(t):
	n = int(input())
	ar = list(map(int, input().split()))
	if 0 in ar:
		print(sum([abs(j) for j in ar]))
	else:
		summ = 0
		for j in ar:
			if j < 0:
				summ += 1
		if summ % 2 == 0:
			print(sum([abs(j) for j in ar]))
		else:
			k = 1000000000
			summ = 0
			for j in ar:
				summ += abs(j)
				if abs(j) < k:
					k = abs(j)
			print(summ - k * 2)


t = int(input())
for i in range(t):
	n = int(input())
	L = list(map(int, input().split()))
	count = 0
	for i in L:
		if 0 > i:
			count += 1
		else:
			pass
	R = []
	for j in L:
		R.append(abs(j))
	if count % 2 == 0:
		answer = sum(R)
	else:
		answer = sum(R) - 2 * min(R)
	print(answer)


for test_case in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	min_abs = 1000000000
	sum_abs = 0
	negative_count = 0
	for i in a:
		if abs(i) < min_abs:
			min_abs = abs(i)
		if i < 0:
			negative_count += 1
		sum_abs += abs(i)
	if negative_count % 2 == 1:
		sum_abs -= 2 * min_abs
	print(sum_abs)


for i in range(int(input())):
	n = int(input())
	mas = list(map(int, input().split()))
	kol = 0
	for j in range(n):
		if mas[j] < 0:
			kol += 1
			mas[j] = abs(mas[j])
	if kol % 2 == 0:
		print(sum(mas))
	else:
		print(sum(mas) - 2 * min(mas))


t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(v) for v in input().split()]
	absarr = [abs(v) for v in arr]
	smallest = min(absarr)
	numberNeg = len([v for v in arr if v < 0])
	numberPos = len(arr) - numberNeg
	if numberNeg % 2 == 0:
		print(sum(absarr))
	else:
		print(sum(absarr) - 2 * smallest)


def op(n, a):
	s = 0
	minn = abs(a[0])
	c = 0
	for i in range(n):
		s += abs(a[i])
		if abs(a[i]) < minn:
			minn = abs(a[i])
		if a[i] < 0:
			c += 1
	if c % 2 == 0:
		return s
	else:
		return s - 2 * minn
t = int(input())
b = []
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b.append(op(n, a))
for i in b:
	print(i)


for _ in range(int(input())):
	input()
	s = list(map(int, input().split()))
	mi = abs(s[0])
	su = 0
	k = 0
	for i in s:
		if i < 0:
			k += 1
		a = abs(i)
		if mi > a:
			mi = a
		su += a
	if k % 2 == 1:
		su -= mi * 2
	print(su)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	for i in a:
		b.append(abs(i))
	non = 0
	for i in a:
		if i < 0:
			non += 1
	if non % 2 == 0:
		print(sum(b))
	else:
		print(sum(b) - 2 * min(b))


t = int(input())
for _ in range(t):
	n = int(input())
	li = list(map(int, input().split()))
	neg = 0
	tot = 0
	for i in li:
		if i < 0:
			neg ^= 1
		tot += abs(i)
	if neg:
		tot -= min([abs(x) for x in li]) * 2
	print(tot)