You are given a rectangular grid with $n$ rows and $m$ columns. The cell located on the $i$-th row from the top and the $j$-th column from the left has a value $a_{ij}$ written in it.

You can perform the following operation any number of times (possibly zero):

Choose any two adjacent cells and multiply the values in them by $-1$. Two cells are called adjacent if they share a side.

Note that you can use a cell more than once in different operations.

You are interested in $X$, the sum of all the numbers in the grid.

What is the maximum $X$ you can achieve with these operations?


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). Description of the test cases follows.

The first line of each test case contains two integers $n$,$m$ ($2 \le n$, $m \le 10$).

The following $n$ lines contain $m$ integers each, the $j$-th element in the $i$-th line is $a_{ij}$ ($-100\leq a_{ij}\le 100$).


-----Output-----

For each testcase, print one integer $X$, the maximum possible sum of all the values in the grid after applying the operation as many times as you want.


-----Examples-----

Input
2
2 2
-1 1
1 1
3 4
0 -1 -2 -3
-1 -2 -3 -4
-2 -3 -4 -5
Output
2
30


-----Note-----

In the first test case, there will always be at least one $-1$, so the answer is $2$.

In the second test case, we can use the operation six times to elements adjacent horizontally and get all numbers to be non-negative. So the answer is: $2\times 1 + 3\times2 + 3\times 3 + 2\times 4 + 1\times 5 = 30$.

Difficulty: EASY
Tags: Mathematics

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	d = 1000000
	c = [0, 0]
	s = 0
	for i in range(n):
		for (j, x) in enumerate(map(int, input().split())):
			y = abs(x)
			s += y
			d = min(d, y)
			if x < 0:
				c[(i + j) % 2] += 1
	if c[0] % 2 == c[1] % 2:
		print(s)
	else:
		print(s - d * 2)


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


def solve(n, m, res):
	ans = 0
	negs = 0
	f = 0
	x = 100000
	for i in range(n):
		for j in range(m):
			if res[i][j] < 0:
				negs += 1
			if res[i][j] == 0:
				f = 1
			ans += abs(res[i][j])
			x = min(x, abs(res[i][j]))
	if f == 1:
		return ans
	elif negs % 2 != 0:
		return ans - 2 * x
	else:
		return ans
t = int(input())
while t:
	(n, m) = map(int, input().split())
	res = []
	for _ in range(n):
		res.append(list(map(int, input().split())))
	print(solve(n, m, res))
	t -= 1


from timeit import timeit
import os, sys
from datetime import datetime
from math import floor, ceil, sqrt, gcd, factorial
from collections import Counter, defaultdict
import bisect

def readint():
	return int(sys.stdin.readline())

def readstr():
	return sys.stdin.readline()

def readlst():
	return list(map(int, sys.stdin.readline().strip().split()))

def readmul():
	return map(int, sys.stdin.readline().strip().split())

def mulfloat():
	return map(float, sys.stdin.readline().strip().split())

def flush():
	return sys.stdout.flush()

def power_two(x):
	return 1 << x

def lcm(a, b):
	return a * b // gcd(a, b)
INF = float('inf')
mod = int(1000000000.0) + 7

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
			return n - leftGreater

def two_pointer(n, val, *arr):
	(l, r, cnt) = (0, n - 1, 0)
	while l < r:
		if arr[l] + arr[r] > val:
			r -= 1
		else:
			cnt += r - l
			l += 1
	return cnt

def lower(arr, n, val):
	(l, r) = (-1, n)
	while r > l + 1:
		m = int(l + r >> 1)
		if arr[m] < val:
			l = m
		else:
			r = m
	return r

def upper(arr, n, val):
	(l, r) = (-1, n)
	while r > l + 1:
		m = int(l + r >> 1)
		if arr[m] <= val:
			l = m
		else:
			r = m
	return l

def binpow(a, n, mod):
	while n:
		if n & 1:
			res = res * a % mod
			n -= 1
		a = a * a % mod
		n = n >> 1
	return res

def check(s):
	cnt = 0
	for i in s:
		if i == '(':
			cnt += 1
		elif i == ')':
			cnt -= 1
	return cnt == 0

def omkar():
	(n, m) = readmul()
	(l, ans) = ([], [])
	cnt = 0
	for i in range(0, n):
		l.append(readlst())
	for i in range(0, n):
		for j in range(0, m):
			if l[i][j] < 0:
				cnt += 1
			ans.append(abs(l[i][j]))
	ans.sort()
	cnt = cnt % 2
	if cnt:
		ans[0] = -ans[0]
	print(sum(ans))
	return

def main():
	test = readint()
	while test:
		omkar()
		test -= 1
main()


import sys, math, itertools, collections, copy
input = sys.stdin.readline

def solve():
	(N, M) = map(int, input().split())
	table = []
	mn = 101
	(flag, neg) = (False, 0)
	for i in range(N):
		arr = list(map(int, input().split()))
		table.append(arr)
		for j in range(M):
			mn = min(mn, abs(table[i][j]))
			if table[i][j] < 0:
				neg += 1
			elif table[i][j] == 0:
				flag = True
	if neg & 1 and flag:
		s = 0
		for i in range(N):
			for j in range(M):
				s += abs(table[i][j])
		print(s)
	elif neg & 1 and (not flag):
		s = 0
		for i in range(N):
			for j in range(M):
				s += abs(table[i][j])
		s -= 2 * abs(mn)
		print(s)
	else:
		s = 0
		for i in range(N):
			for j in range(M):
				s += abs(table[i][j])
		print(s)
for _ in range(int(input())):
	solve()


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


from collections import defaultdict, deque
t = int(input())
for i in range(t):
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	counter = 0
	mi = float('inf')
	flag = 0
	for i in range(n):
		arr = list(map(int, input().split()))
		for i in arr:
			counter += abs(i)
			mi = min(mi, abs(i))
			if i < 0:
				flag ^= 1
	if not flag:
		print(counter)
	else:
		print(counter - 2 * mi)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split(' '))
	a = [list(map(int, input().split(' '))) for _ in range(n)]
	sum = 0
	neg = 0
	minn = 101
	for i in range(n):
		for j in range(m):
			if a[i][j] < 0:
				neg += 1
			sum += abs(a[i][j])
			minn = min(minn, abs(a[i][j]))
	if neg % 2 == 1:
		print(sum - 2 * minn)
	else:
		print(sum)


for _ in range(int(input())):
	(n, m) = [int(i) for i in input().split()]
	l = []
	for i in range(n):
		l.append(list(map(int, input().split())))
	ans = 0
	least = int(1000000000.0)
	exist = 0
	for i in range(n):
		for j in range(m):
			ans += abs(l[i][j])
			least = min(least, abs(l[i][j]))
			if l[i][j] < 0:
				exist += 1
	if exist % 2 == 1:
		print(ans - 2 * least)
	else:
		print(ans)


def count_negative(matrix):
	count = 0
	for i in range(len(matrix)):
		for j in range(len(matrix[0])):
			count += matrix[i][j] <= 0
	return count

def matrix_sum(matrix):
	summa = 0
	for i in range(len(matrix)):
		for j in range(len(matrix[0])):
			summa += abs(matrix[i][j])
	return summa

def matrix_min(matrix):
	minimum = matrix[0][0]
	for i in range(len(matrix)):
		for j in range(len(matrix[0])):
			minimum = minimum if abs(matrix[i][j]) > abs(minimum) else matrix[i][j]
	return minimum
matrices = []
length = int(input())
for _ in range(length):
	(n, m) = map(int, input().split())
	matrix = []
	for i in range(n):
		matrix.append(list(map(int, input().split())))
	matrices.append(matrix)
for matrix in matrices:
	delta = 0 if count_negative(matrix) % 2 == 0 else 2 * abs(matrix_min(matrix))
	print(matrix_sum(matrix) - delta)


import sys
input = sys.stdin.buffer.readline
ri = lambda : int(input())
rl = lambda : list(map(int, input().split()))
rs = lambda : input().decode().rstrip('\n\r')
wrt = sys.stdout.write
pr = lambda *args, end='\n': wrt(' '.join([str(x) for x in args]) + end)
xrange = lambda args: reversed(range(args))
cdiv = lambda x, y: -(-x // y)
enum = enumerate
inf = float('inf')
mod = 10 ** 9 + 7
from collections import defaultdict as dd
Cases = ri()
for Case in range(Cases):
	(n, m) = rl()
	small = inf
	zp = False
	su = 0
	neg = -inf
	cnt = 0
	for i in range(n):
		temp = rl()
		su += sum([abs(i) for i in temp])
		for i in temp:
			small = min(small, abs(i))
			if i < 0:
				neg = max(neg, i)
				cnt += 1
			if i == 0:
				zp = True
	if zp or cnt % 2 == 0:
		print(su)
	else:
		print(su - 2 * small)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	lst = []
	for _ in range(n):
		lst.append(list(map(int, input().split())))
	negCount = 0
	tot = 0
	smallest = float('inf')
	zeroExists = False
	for i in range(n):
		for j in range(m):
			if lst[i][j] == 0:
				zeroExists = True
			elif lst[i][j] < 0:
				negCount += 1
			smallest = min(smallest, abs(lst[i][j]))
			tot += abs(lst[i][j])
	if zeroExists:
		print(tot)
	elif negCount % 2 == 1:
		print(tot - 2 * smallest)
	else:
		print(tot)


for i in range(int(input())):
	arr = list(map(int, input().split()))
	n = arr[0]
	m = arr[1]
	st = 0
	s = 0
	mn = 10 ** 9
	for j in range(n):
		row = list(map(int, input().split()))
		s += sum([1 if k < 0 else 0 for k in row])
		row = list(map(abs, row))
		st += sum(row)
		mn = min(mn, min(row))
	if s % 2 == 0:
		print(st)
	else:
		st = st - 2 * mn
		print(st)


f = lambda : [*map(int, input().split())]
for _ in range(f()[0]):
	(r, c) = f()
	sum = count = 0
	num = 90000000000.0
	for i in range(r):
		for x in f():
			sum += abs(x)
			num = min(num, abs(x))
			count += x < 0
	print(sum - 2 * num * (count % 2))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		b = list(map(int, input().split()))
		l.append(b)
	(s, negatives, m) = (0, 0, abs(l[0][0]))
	for i in range(len(l)):
		for j in range(len(l[0])):
			if l[i][j] < 0:
				negatives += 1
			if abs(l[i][j]) <= m:
				m = abs(l[i][j])
			s += abs(l[i][j])
	if negatives % 2 == 0:
		print(s)
	else:
		print(s - 2 * m)


numbertests = int(input(''))
tests = []
for test in range(0, numbertests):
	test = []
	r = int(input('').split(' ')[0])
	for r in range(0, r):
		row = input('').split(' ')
		test.append(row)
	tests.append(test)
for test in tests:
	for r in range(0, len(test)):
		for c in range(0, len(test[r])):
			test[r][c] = int(test[r][c])
for test in tests:
	numbernegatives = 0
	abssum = 0
	abslowest = abs(test[0][0])
	for r in range(0, len(test)):
		for c in range(0, len(test[0])):
			if test[r][c] < 0:
				numbernegatives += 1
			if abs(test[r][c]) < abslowest:
				abslowest = abs(test[r][c])
			abssum += abs(test[r][c])
	if numbernegatives % 2 == 0:
		print(abssum)
	else:
		print(abssum - abs(abslowest) * 2)


import sys, os
from math import sqrt, gcd, ceil, log, floor
from bisect import bisect, bisect_left
from collections import defaultdict, Counter, deque
from heapq import heapify, heappush, heappop
from itertools import permutations
input = sys.stdin.readline
read = lambda : list(map(int, input().strip().split()))
MOD = 10 ** 9 + 7

def main():
	for _ in range(int(input())):
		(n, m) = read()
		mat = []
		for i in range(n):
			mat.append(read())
		mini = 10 ** 9
		count = 0
		s = 0
		z = 0
		for i in range(n):
			for j in range(m):
				if mat[i][j] < 0:
					count += 1
				mini = min(mini, abs(mat[i][j]))
				s += abs(mat[i][j])
				z |= mat[i][j] == 0
		if count % 2 == 1:
			if z:
				print(s)
			else:
				print(s - 2 * mini)
		else:
			print(s)
main()


import sys
inp = sys.stdin.readline
for _ in range(int(inp())):
	(n, m) = map(int, inp().split())
	data = [list(map(int, inp().split())) for i in range(n)]
	zero = False
	min_abs = sys.maxsize
	cnt = 0
	s = 0
	for i in range(n):
		for j in range(m):
			tmp = data[i][j]
			min_abs = min(min_abs, abs(tmp))
			if tmp < 0:
				cnt += 1
				s += -tmp
			elif tmp > 0:
				s += tmp
			else:
				zero = True
	if zero or cnt % 2 == 0:
		print(s)
	else:
		print(s - 2 * min_abs)


count = int(input())
result = []

def minus_counter(n, m, matr):
	counter = 0
	for i in range(n):
		for j in range(m):
			matr[i][j] = int(matr[i][j])
			if matr[i][j] < 0:
				counter += 1
	return counter

def find_min(n, m, matr):
	min_item = abs(matr[0][0])
	for i in range(n):
		for j in range(m):
			if abs(matr[i][j]) < min_item:
				min_item = abs(matr[i][j])
	return min_item

def sum_matr(n, m, matr):
	s = 0
	for i in range(n):
		for j in range(m):
			s += abs(matr[i][j])
	return s
for _ in range(count):
	(n, m) = map(int, input().split())
	matr = []
	for i in range(n):
		tmp = input()
		tmp = tmp.split(' ')
		matr.append(tmp)
	minus = minus_counter(n, m, matr)
	s = sum_matr(n, m, matr)
	if minus % 2 == 1:
		s -= 2 * find_min(n, m, matr)
	result.append(s)
for i in range(count):
	print(result[i])


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


def read_matrix():
	temp_matrix = []
	for i in range(n):
		temp_matrix.append(list(map(int, input().split())))
	return temp_matrix
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	matrix = read_matrix()
	neg_count = 0
	min_min_el = (0, 0)
	for y in range(n):
		min_el = 0
		negatives = 0
		for x in range(m):
			if matrix[y][x] < 0:
				negatives += 1
				matrix[y][x] *= -1
			if matrix[y][x] < matrix[y][min_el]:
				min_el = x
		if negatives % 2 != 0:
			neg_count += 1
		if matrix[y][min_el] < matrix[min_min_el[0]][min_min_el[1]]:
			min_min_el = (y, min_el)
	if neg_count % 2 != 0:
		matrix[min_min_el[0]][min_min_el[1]] *= -1
	ans = 0
	for y in range(n):
		ans += sum(matrix[y])
	print(ans)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	neg = 0
	sume = 0
	mini = float('inf')
	zero = 0
	for i in range(n):
		arr = list(map(int, input().split()))
		for j in arr:
			if j < 0:
				neg += 1
			if j == 0:
				zero = 1
			sume += abs(j)
			mini = min(mini, abs(j))
	if not zero and neg % 2:
		print(sume - 2 * mini)
	else:
		print(sume)


for t in range(int(input())):
	(r, c) = map(int, input().split())
	l1 = []
	neg = 0
	min1 = []
	sum1 = 0
	for i in range(r):
		temp = list(map(int, input().split()))
		for i in range(c):
			if temp[i] < 0:
				neg += 1
				temp[i] *= -1
		min1.append(min(temp))
		sum1 += sum(temp)
		l1.append(temp)
	if neg % 2 == 0:
		print(sum1)
	elif neg % 2 != 0:
		print(sum1 - 2 * min(min1))


for _ in range(int(input())):
	(n, a) = list(map(int, input().strip().split()))
	mat = []
	m = 10 ** 9
	count = 0
	ans = 0
	for i in range(n):
		mat.append(list(map(int, input().strip().split())))
		for j in range(a):
			ans += abs(mat[i][j])
			if mat[i][j] < 0:
				count += 1
			m = min(m, abs(mat[i][j]))
	if count % 2 == 0:
		print(ans)
	else:
		print(ans - 2 * m)


def solve(n, m):
	arr = []
	neg = []
	k = 1000
	for i in range(n):
		cur = list(map(int, input().split()))
		arr.extend(cur)
		for x in cur:
			if x < 0:
				neg.append(x)
			else:
				k = min(k, x)
	if not neg:
		return sum(arr)
	if len(neg) % 2 == 0:
		return sum(arr) - 2 * sum(neg)
	if -max(neg) > k:
		return sum(arr) - 2 * sum(neg) - 2 * k
	return sum(arr) - 2 * sum(neg) + 2 * max(neg)
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	print(solve(n, m))


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	x = []
	for i in range(n):
		l = list(map(int, input().split()))
		x += l
	zero = 0
	neg = []
	positive = 0
	ans = [abs(i) for i in x]
	if 0 in x:
		print(sum(ans))
	else:
		for j in x:
			if j >= 0:
				positive += j
			else:
				neg.append(j)
		if len(neg) % 2 == 0:
			answer = positive + -1 * sum(neg)
			print(answer)
		else:
			mini = min(ans)
			print(sum(ans) - 2 * mini)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	c = 0
	arr = []
	for _ in range(n):
		l = list(map(int, input().split()))
		arr += l
		for el in l:
			if el < 0:
				c += 1
	arr.sort()
	if c % 2 == 0:
		print(sum((abs(el) for el in arr)))
	else:
		p = []
		for el in arr:
			p.append(abs(el))
		p.sort()
		print(sum(p) - 2 * p[0])


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	tot = []
	sumn = 0
	sumtot = 0
	for _ in range(n):
		b = list(map(int, input().split()))
		for j in b:
			if j < 0:
				sumn += 1
				sumtot -= j
				tot.append(-j)
			else:
				sumtot += j
				tot.append(j)
	if sumn % 2 == 0:
		print(sumtot)
	else:
		print(sumtot - 2 * min(tot))


from math import *
a = int(input())
for x in range(a):
	(b, c) = map(int, input().split())
	d = []
	for y in range(b):
		j = list(map(int, input().split()))
		d.append(j)
	s = 0
	mi = 999999999999
	n = 0
	for y in range(b):
		for z in range(c):
			if d[y][z] <= 0:
				s += 1
			if abs(d[y][z]) < mi:
				mi = abs(d[y][z])
			n += abs(d[y][z])
	if s % 2 == 0:
		print(n)
	else:
		print(n - 2 * mi)


from collections import deque as de
import math
from collections import Counter as cnt
from functools import reduce
from typing import MutableMapping
from itertools import groupby as gb
from fractions import Fraction as fr

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

class My_stack:

	def __init__(self):
		self.data = []

	def my_push(self, x):
		return self.data.append(x)

	def my_pop(self):
		return self.data.pop()

	def my_peak(self):
		return self.data[-1]

	def my_contains(self, x):
		return self.data.count(x)

	def my_show_all(self):
		return self.data

	def isEmpty(self):
		return len(self.data) == 0
arrStack = My_stack()

def decimalToBinary(n):
	return bin(n).replace('0b', '')

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def get_prime_factors(number):
	prime_factors = []
	while number % 2 == 0:
		prime_factors.append(2)
		number = number / 2
	for i in range(3, int(math.sqrt(number)) + 1, 2):
		while number % i == 0:
			prime_factors.append(int(i))
			number = number / i
	if number > 2:
		prime_factors.append(int(number))
	return prime_factors

def get_frequency(list):
	dic = {}
	for ele in list:
		if ele in dic:
			dic[ele] += 1
		else:
			dic[ele] = 1
	return dic

def Log2(x):
	return math.log10(x) / math.log10(2)

def isPowerOfTwo(n):
	return math.ceil(Log2(n)) == math.floor(Log2(n))

def ceildiv(x, y):
	return (x + y - 1) // y
t = int(input())
while t:
	t -= 1
	(n, m) = map(int, input().split())
	l = [list(map(int, input().split())) for i in range(n)]
	negativecount = 0
	sum = 0
	mn = 1000
	for i in range(n):
		for j in range(m):
			if l[i][j] <= 0:
				negativecount += 1
			sum += abs(l[i][j])
			if abs(l[i][j]) < mn:
				mn = abs(l[i][j])
	if negativecount % 2:
		print(sum - 2 * mn)
	else:
		print(sum)


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


for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	l = [list(map(int, input().split())) for i in range(n)]
	ans = 0
	c = 0
	o = []
	for i in l:
		x = sorted(i, key=lambda x: abs(x))
		for j in x:
			if j < 0:
				c = c + 1
		o.append(abs(x[0]))
	if c % 2 == 0:
		for i in l:
			for j in i:
				ans = ans + abs(j)
		print(ans)
	else:
		for i in l:
			for j in i:
				ans = ans + abs(j)
		print(ans - 2 * min(o))


l = lambda : map(int, input().split())
p = lambda : int(input())
ss = lambda : input()
from math import ceil
for _ in range(p()):
	(n, m) = l()
	f = 0
	c = 0
	t = 100000000000
	for i in range(n):
		a = list(l())
		a.sort()
		s = 0
		for j in range(m):
			if a[j] <= 0:
				c += 1
			f += abs(a[j])
			t = min(t, abs(a[j]))
	if c % 2:
		f -= 2 * t
	print(f)


import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

def gift():
	for _ in range(t):
		(n, m) = list(map(int, input().split()))
		ans = []
		for i in range(n):
			ans.append(list(map(int, input().split())))
		absVal = []
		minusCount = 0
		gotZ = False
		for i in range(n):
			for j in range(m):
				if ans[i][j] < 0:
					minusCount += 1
				elif ans[i][j] == 0:
					gotZ = True
				absVal.append(abs(ans[i][j]))
		if gotZ:
			yield sum(absVal)
		else:
			absVal.sort()
			if minusCount % 2 == 0:
				yield sum(absVal)
			else:
				yield (sum(absVal[1:]) - sum(absVal[:1]))
t = int(input())
ans = gift()
print(*ans, sep='\n')


import os, sys
from io import BytesIO, IOBase

def main():
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		arr = [list(map(int, input().split())) for _ in range(n)]
		su = 0
		fl = 0
		z = 10 ** 10
		for i in range(n):
			for j in range(m):
				if arr[i][j] < 0:
					fl += 1
				su += abs(arr[i][j])
				z = min(z, abs(arr[i][j]))
		if fl % 2:
			print(su - 2 * z)
		else:
			print(su)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


t = int(input())
while t > 0:
	(n, m) = [int(x) for x in input().split(' ')]
	(add, minus, value) = (0, 0, 100000)
	for i in range(n):
		a = [int(x) for x in input().split(' ')]
		for j in range(m):
			if a[j] < 0:
				minus += 1
			value = min(value, abs(a[j]))
			add += abs(a[j])
	if minus % 2 != 0:
		add -= 2 * value
	print(add)
	t -= 1


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	arr = list()
	for i in range(n):
		temp = [int(j) for j in input().split()]
		arr.append(temp)
	sm = 0
	count = 0
	mn = float('inf')
	for i in range(n):
		for j in range(m):
			sm += abs(arr[i][j])
			if arr[i][j] <= 0:
				count += 1
			mn = min(mn, abs(arr[i][j]))
	if count % 2 != 0:
		sm = sm - 2 * abs(mn)
	print(sm)


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


t = int(input())
answers = []
for _ in range(t):
	nm = input().split()
	grid = []
	x = 0
	y = 0
	negatives = []
	positives = []
	numbers = []
	for i in range(int(nm[0])):
		row = input().split()
		grid.append(row)
	for j in range(int(nm[0])):
		for k in range(int(nm[1])):
			if int(grid[j][k]) > 0:
				positives.append(int(grid[j][k]))
				numbers.append(abs(int(grid[j][k])))
			else:
				y += 1
				negatives.append(int(grid[j][k]))
				numbers.append(abs(int(grid[j][k])))
	if y % 2 == 0:
		x = sum(numbers)
	else:
		z = min(numbers)
		x = sum(numbers) - 2 * z
	answers.append(x)
for m in range(t):
	print(answers[m])


import math
import collections
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	for a in range(n):
		l1 = list(map(int, input().split()))
		l.append(l1)
	ans = 0
	m1 = []
	count = 0
	mini = math.inf
	for i in range(n):
		for j in range(m):
			if l[i][j] < 0:
				count += 1
				mini = min(mini, -l[i][j])
				ans += -l[i][j]
			else:
				mini = min(mini, abs(l[i][j]))
				ans += abs(l[i][j])
	if count % 2 == 0:
		print(ans)
	else:
		print(ans - 2 * mini)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	mx = []
	a = 0
	b = 0
	for i in range(n):
		y = list(map(int, input().split()))
		for j in range(m):
			l = y[j]
			if l < 0:
				a += 1
			if l == 0:
				b += 1
			mx.append(abs(l))
	u = a + b
	if a % 2 == 0 or (a + b) % 2 == 0:
		s = 0
		for i in range(len(mx)):
			s += mx[i]
		print(s)
	else:
		s = 0
		mx.sort()
		for i in range(1, len(mx)):
			s += mx[i]
		print(s - mx[0])


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = [list(map(int, input().split())) for i in range(n)]
	(mi, ans, c, f) = (101, 0, 0, 0)
	for i in l:
		for j in i:
			if j < 0:
				c += 1
			if j == 0:
				f = 1
			ans += abs(j)
			mi = min(mi, abs(j))
	if f:
		print(ans)
	elif c % 2:
		print(ans - 2 * abs(mi))
	else:
		print(ans)


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


for i in range(int(input())):
	(n, m) = map(int, input().split())
	k = []
	for i in range(n):
		m = list(map(int, input().split()))
		k += m
	z = []
	p = []
	n = []
	for i in k:
		if i > 0:
			p.append(i)
		elif i < 0:
			n.append(abs(i))
		else:
			z.append(i)
	t = sum(p) + sum(n) + sum(z)
	if len(z) == 0:
		if len(n) % 2 == 0:
			print(t)
		elif len(p) == 0:
			print(t - 2 * min(n))
		elif len(n) == 0:
			print(t - 2 * min(p))
		else:
			print(t - 2 * min(min(p), min(n)))
	else:
		print(t)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	mn = 1000
	x = 0
	nc = 0
	for i in range(n):
		for j in map(int, input().split()):
			if j < 0:
				nc = 1 - nc
			if abs(j) < mn:
				mn = abs(j)
			x += abs(j)
	ans = x - 2 * mn * nc
	print(ans)


for ct in range(int(input())):
	(n, m) = map(int, input().split())
	grid = [list(map(int, input().split())) for i in range(n)]
	absoluteSum = negativeCount = 0
	minimumValue = abs(grid[0][0])
	for i in range(n):
		for j in range(m):
			absoluteSum += abs(grid[i][j])
			minimumValue = min(minimumValue, abs(grid[i][j]))
			negativeCount += grid[i][j] < 0
	print(absoluteSum - 2 * minimumValue * (negativeCount % 2))


x = int(input())
while x > 0:
	x = x - 1
	(c, d) = map(int, input().split())
	zero_flag = False
	neg = 0
	h = []
	minall = 99999999
	for i in range(c):
		k = list(map(int, input().split()))
		for i in k:
			if i == 0:
				zero_flag = True
			if i < 0:
				neg += 1
			if minall > abs(i):
				minall = abs(i)
		h.append(k)
	sum1 = 0
	if zero_flag == True:
		for j in h:
			for i in j:
				sum1 += abs(i)
	if zero_flag == False:
		for j in h:
			for i in j:
				sum1 += abs(i)
		if neg % 2 == 1:
			sum1 = sum1 - 2 * minall
	print(sum1)


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


t = int(input())
for i in range(t):
	(n, m) = [int(j) for j in input().split()]
	l = []
	temp = []
	zero = 0
	for j in range(n):
		l.append([int(k) for k in input().split()])
		for k in range(m):
			temp.append(abs(l[-1][k]))
			if l[-1][k] == 0:
				zero += 1
	sum = 0
	neg = 0
	for j in range(n):
		for k in range(m):
			sum += abs(l[j][k])
			if l[j][k] < 0:
				neg += 1
	if zero or neg == 0:
		print(sum)
	else:
		temp.sort()
		sum1 = 0
		for j in range(n * m):
			sum1 = temp[j] + sum1
		if neg % 2 == 0:
			print(sum1)
		else:
			print(sum1 - 2 * temp[0])


t = int(input())
while t > 0:
	t -= 1
	(n, m) = [int(x) for x in input().split()]
	arr = []
	countneg = 0
	countzero = 0
	for i in range(n):
		a = [int(x) for x in input().split()]
		for item in a:
			if item < 0:
				countneg += 1
			elif item == 0:
				countzero += 1
		arr.append(a)
	ans = 0
	arr1 = []

	def sumt():
		a = 0
		for i in range(n):
			for j in range(m):
				a += abs(arr[i][j])
		return a
	if countneg % 2 == 0:
		ans = sumt()
	elif countzero != 0:
		ans = sumt()
	else:
		for i in range(n):
			for j in range(m):
				arr1.append(abs(arr[i][j]))
		arr1.sort()
		leastneg = arr1[0]
		ans = sumt() - leastneg - leastneg
	print(ans)


s = int(input())
answer = ''
while s > 0:
	x = 0
	a_m = 100
	odds = 0
	n = int(input().split()[0])
	while n > 0:
		for i in map(int, input().split()):
			if i < 0:
				odds += 1
				i = i * -1
			if i < a_m:
				a_m = i
			x += i
		n -= 1
	s -= 1
	if a_m != 0 and odds % 2:
		x -= 2 * a_m
	answer += str(x) + '\n'
print(answer)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	k = [] * n
	ng = 0
	p = 0
	mn = 1000000000
	xx = 0
	for i in range(n):
		l = []
		s = list(map(int, input().split()))
		for j in s:
			xx += abs(j)
			if abs(j) < mn:
				mn = abs(j)
			if j <= 0:
				ng += 1
			l.append(j)
		k.append(l)
	if ng % 2 == 0:
		print(xx)
	else:
		print(xx - 2 * mn)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	lst = [list(map(int, input().split())) for _ in range(n)]
	tot = 0
	zer = 0
	for i in lst:
		if 0 in i:
			zer = 1
			break
	if zer == 1:
		for i in lst:
			for e in i:
				tot += abs(e)
		print(tot)
	else:
		minv = abs(lst[0][0])
		ans = []
		tot = 0
		for i in range(n):
			for e in range(m):
				if abs(lst[i][e]) < minv:
					minv = abs(lst[i][e])
				if lst[i][e] > 0:
					tot += abs(lst[i][e])
				else:
					ans.append(lst[i][e])
					tot += abs(lst[i][e])
		if len(ans) % 2 == 0:
			print(tot)
		else:
			print(tot - 2 * abs(minv))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(w, c) = ([], 0)
	for _ in range(n):
		w += list(map(int, input().split()))
	w.sort()
	for i in w:
		if i < 0:
			c += 1
		if i >= 0:
			break
	w = sorted(map(abs, w))
	if c % 2 == 0:
		print(sum(w))
	else:
		print(sum(w[1:]) - w[0])


for i in range(int(input())):
	arr = input().split(' ')
	arr = list(map(int, arr))
	L = []
	for j in range(arr[0]):
		arr1 = input().split(' ')
		arr1 = list(map(int, arr1))
		L.extend(arr1)
	s = 0
	for k in L:
		if k < 0:
			s += 1
	absList = list(map(abs, L))
	if s % 2 == 0:
		print(sum(absList))
	else:
		print(sum(absList) - min(absList) * 2)


f_lamb = lambda : map(int, input().split())
for o in range(int(*f_lamb())):
	(n, m) = f_lamb()
	(g, k) = ([], 0)
	for p in range(n):
		g += [*f_lamb()]
	for i in range(n * m):
		if g[i] < 0:
			k += 1
			g[i] *= -1
	print(sum(g) - k % 2 * min(g) * 2)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	index = 0
	c = 0
	S = 0
	valid = 1
	Min = 101
	while index < n:
		L = list(map(int, input().split()))
		I = 0
		while I < m:
			if valid:
				if L[I] == 0:
					valid = 0
					c = -1
				if L[I] < 0:
					c += 1
			S += abs(L[I])
			if abs(L[I]) < Min:
				Min = abs(L[I])
			I += 1
		index += 1
	if valid:
		if c % 2 == 0:
			print(S)
		else:
			print(S - 2 * Min)
	else:
		print(S)


import sys, os, io

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

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions, statistics
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal
from sys import stdout
from heapq import heappush, heappop, heapify, _heapify_max, _heappop_max, nsmallest, nlargest

def main():
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	tc = ri()
	for _ in range(tc):
		(n, m) = ria()
		a = []
		neg = 0
		s = 0
		mi = 93042233333333333333333333
		t = 0
		for i in range(n):
			g = ria()
			for j in g:
				if j <= 0:
					neg += 1
				mi = min(mi, abs(j))
				s += abs(j)
			a.append(g)
		if neg % 2 != 0:
			print(s - 2 * mi)
		else:
			print(s)
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

	def flush(self):
		os.write(self._fd, self.buffer.getvalue())
		(self.buffer.truncate(0), self.buffer.seek(0))

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


for i in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		a.append(list(map(int, input().split())))
	p = abs(a[0][0])
	(c, s, k) = (0, 0, 0)
	for i in range(n):
		for j in range(m):
			if a[i][j] == 0:
				k = 1
			elif a[i][j] < 0:
				c += 1
			s += abs(a[i][j])
			if abs(a[i][j]) < p:
				p = abs(a[i][j])
	if k == 1 or c % 2 == 0:
		print(s)
	else:
		print(s - 2 * p)


for _ in range(int(input())):
	(r, c) = map(int, input().split())
	(count, mn) = (0, 100)
	ans = 0
	for i in range(r):
		k = list(map(int, input().split()))
		for j in k:
			if j < 0:
				count += 1
			mn = min(mn, abs(j))
			ans += abs(j)
	if count % 2 == 0:
		print(ans)
	else:
		print(ans - 2 * mn)


T = int(input())
ans = []
for t in range(T):
	(n, m) = map(int, input().split())
	tmp = []
	for i in range(n):
		x = list(map(int, input().split()))
		tmp = tmp + x
	minuscount = 0
	for i in range(len(tmp)):
		if tmp[i] < 0:
			minuscount += 1
		if tmp[i] == 0:
			minuscount = 0
			break
	for i in range(len(tmp)):
		tmp[i] = abs(tmp[i])
	if minuscount % 2 == 0:
		ans.append(sum(tmp))
	else:
		ans.append(sum(tmp) - 2 * min(tmp))
for t in range(T):
	print(ans[t])


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


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		a.append(list(map(int, input().split())))
	(mn, c, z, s) = (100000, 0, 0, 0)
	for i in range(n):
		for j in range(m):
			if a[i][j] < 0:
				c += 1
			if a[i][j] == 0:
				z = 1
			mn = min(mn, abs(a[i][j]))
			s += abs(a[i][j])
	if z:
		print(s)
	elif c & 1:
		print(s - mn * 2)
	else:
		print(s)


for T in range(int(input())):
	(n, m) = map(int, input().split())
	a = [list(map(int, input().split()[:m])) for i in range(n)]
	neg_count = 0
	zero_count = False
	(s, m) = (0, 100)
	for i in range(n):
		for val in a[i]:
			if val < 0:
				neg_count += 1
			if val == 0:
				zero_count = True
			s += abs(val)
			if m > abs(val) and val != 0:
				m = abs(val)
	if neg_count & 1 == 0:
		print(s)
	elif zero_count:
		print(s)
	else:
		print(s - 2 * m)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	array = [[int(i) for i in input().split()] for j in range(n)]
	count = 0
	mini = 10 ** 10
	sumo = 0
	for i in range(n):
		for j in range(m):
			if array[i][j] < 0:
				count += 1
			sumo += abs(array[i][j])
			mini = min(abs(array[i][j]), mini)
	if count % 2 == 0:
		print(sumo)
	else:
		print(sumo - 2 * mini)


import sys
input = sys.stdin.readline
t = int(input())
for tests in range(t):
	(n, m) = map(int, input().split())
	A = [list(map(int, input().split())) for i in range(n)]
	PLUS = []
	MINUS = []
	ALL = []
	for i in range(n):
		for j in range(m):
			if A[i][j] > 0:
				PLUS.append(A[i][j])
			else:
				MINUS.append(-A[i][j])
			ALL.append(abs(A[i][j]))
	if len(MINUS) % 2 == 0:
		print(sum(PLUS) + sum(MINUS))
	else:
		print(sum(PLUS) + sum(MINUS) - min(ALL) * 2)


T = int(input())
for _ in range(T):
	(n, m) = map(int, input().split())
	a = []
	c = 0
	for i in range(n):
		lis = list(map(int, input().split()))
		for j in lis:
			if j < 0:
				c += 1
			a.append(abs(j))
	a.sort()
	if c % 2:
		print(sum(a) - 2 * a[0])
		continue
	print(sum(a))


from sys import stdin, stdout
input = stdin.readline
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	mat = [0 for x in range(n)]
	for i in range(n):
		mat[i] = [int(x) for x in input().split()]
	a = 0
	val = 0
	m1 = float('inf')
	for i in range(n):
		for j in range(m):
			val += abs(mat[i][j])
			m1 = min(m1, abs(mat[i][j]))
			if mat[i][j] < 0:
				a += 1
	if a % 2 == 0:
		print(val)
	else:
		print(val - 2 * m1)


N = int(input())
for _ in range(N):
	(n, m) = map(int, input().split())
	a = list()
	for i in range(n):
		a += list(map(int, input().split()))
	a.sort()
	minAbs = 101
	countNegative = 0
	for i in range(len(a)):
		if a[i] <= 0:
			countNegative += 1
			a[i] = -a[i]
		if a[i] < minAbs:
			minAbs = a[i]
	if countNegative % 2 == 1:
		print(sum(a) - minAbs * 2)
	else:
		print(sum(a))


import sys
input = sys.stdin.readline
print = sys.stdout.write
ri = lambda : int(input())
rl = lambda : list(map(int, input().split()))
rs = lambda : input()
for _ in range(ri()):
	(n, m) = rl()
	grid = []
	for _ in range(n):
		grid.append(rl())
	c = 0
	s = 0
	M = float('inf')
	for i in range(n):
		for j in range(m):
			if grid[i][j] < 0:
				c += 1
			s += abs(grid[i][j])
			M = min(M, abs(grid[i][j]))
	if c % 2:
		ans = s - 2 * M
	else:
		ans = s
	print('%d\n' % ans)


from math import *
for u in range(int(input())):
	(n, m) = map(int, input().split())
	c = 0
	ka = inf
	s = 0
	for w in range(n):
		l = list(map(int, input().split()))
		for i in range(m):
			if l[i] < 0:
				c += 1
			s += abs(l[i])
			ka = min(abs(l[i]), ka)
	if c % 2 == 0:
		print(s)
	else:
		print(s - 2 * ka)


t = int(input())
for i in range(t):
	(r, c) = input().split()
	r = int(r)
	c = int(c)
	m = []
	for i in range(0, r):
		m.append([int(j) for j in input().split()])
	m = sum(m, [])
	a = r * c
	b = 0
	i = 0
	n = []
	for i in range(a):
		if m[i] < 0:
			b += 1
			c = -1 * m[i]
			n.append(c)
		else:
			n.append(m[i])
		i += 1
	if b % 2 == 0:
		k = sum(n)
		print(k)
	else:
		n.sort()
		s = min(n)
		s = -1 * s
		n.remove(min(n))
		n.append(s)
		k = sum(n)
		print(k)


I = input
for _ in [0] * int(I()):
	s = ' '.join((I() for _ in [0] * int(I().split()[0])))
	a = (*map(abs, map(int, s.split())),)
	print(sum(a) - s.count('-') % 2 * 2 * min(a))


t = int(input())
while t != 0:
	x = input()
	x = x.split()
	r = int(x[0])
	c = int(x[1])
	sum = 0
	cnt = 0
	l = 100000
	for i in range(r):
		x = input()
		x = x.split()
		for j in range(c):
			sum += abs(int(x[j]))
			if int(x[j]) <= 0:
				cnt += 1
			l = min(l, abs(int(x[j])))
	if cnt % 2:
		print(sum - 2 * l)
	else:
		print(sum)
	t -= 1


t = int(input().strip())
for _ in range(t):
	(n, m) = map(int, input().strip().split())
	ans = []
	for i in range(n):
		ans.extend([int(i) for i in input().strip().split()])
	if 0 in ans:
		for i in range(len(ans)):
			ans[i] = max(ans[i], -ans[i])
		print(sum(ans))
	else:
		cnt = 0
		for i in range(len(ans)):
			if ans[i] < 0:
				cnt += 1
			ans[i] = max(ans[i], -ans[i])
		if cnt % 2:
			print(sum(ans) - 2 * min(ans))
		else:
			print(sum(ans))


import math
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		l.append(list(map(int, input().split())))
	z = 0
	mi = 1000
	s = 0
	for i in range(n):
		for j in range(m):
			s += abs(l[i][j])
			if l[i][j] < 0:
				z += 1
			if abs(l[i][j]) < mi:
				mi = min(mi, abs(l[i][j]))
	if z % 2 == 0:
		print(s)
	else:
		print(s - 2 * mi)


for t in range(int(input())):
	(row, col) = map(int, input().split())
	matrix = []
	for r in range(row):
		matrix.append(list(map(int, input().split())))
	(mi, mx) = (float('inf'), float('-inf'))
	(neg, s) = (0, 0)
	for r in range(row):
		for c in range(col):
			ele = abs(matrix[r][c])
			s += ele
			mi = min(mi, ele)
			mx = max(mx, ele)
			if matrix[r][c] < 0:
				neg += 1
	if neg % 2 == 0:
		print(s)
	else:
		print(s - mi - mi)


t = int(input())
for _ in range(t):
	(x, y) = map(int, input().split())
	m = []
	for i in range(x):
		l = list(map(int, input().split()))
		m.append(l)
	n = 0
	p = 0
	z = 0
	nsum = 0
	psum = 0
	minn = abs(m[0][0])
	for i in range(x):
		for j in range(y):
			if minn > abs(m[i][j]):
				minn = abs(m[i][j])
			if m[i][j] == 0:
				z += 1
			elif m[i][j] < 0:
				n += 1
				nsum += m[i][j]
			elif m[i][j] > 0:
				p += 1
				psum += m[i][j]
	if z == 0 and n % 2 == 1:
		print(psum - nsum - 2 * minn)
	else:
		print(psum - nsum)


from sys import stdin, gettrace
if gettrace():
	inputi = input
else:

	def input():
		return next(stdin)[:-1]

	def inputi():
		return stdin.buffer.readline()

def solve():
	(n, m) = map(int, input().split())
	aa = []
	for _ in range(n):
		aa += [int(a) for a in input().split()]
	abssum = 0
	nc = 0
	mn = 100
	for a in aa:
		abssum += abs(a)
		mn = min(abs(a), mn)
		if a < 0:
			nc += 1
	if 0 in aa or nc % 2 == 0:
		print(abssum)
	else:
		print(abssum - 2 * mn)

def main():
	t = int(input())
	for _ in range(t):
		solve()
main()


for _ in range(int(input())):
	(row, columns) = map(int, input().split())
	min_count = summation = 0
	minimum = 2 ** 32
	for k in range(0, row):
		row_elems = list(map(int, input().split()))
		for j in row_elems:
			if j < 0:
				min_count = min_count + 1
			minimum = min(minimum, abs(j))
			summation += abs(j)
	if min_count % 2 == 0:
		print(summation)
	else:
		print(summation - 2 * minimum)


from sys import stdin, maxsize
for i in range(int(stdin.readline())):
	(n, m) = [int(x) for x in stdin.readline().split()]
	l = [[0] * m for j in range(0, n)]
	mi = maxsize
	su = 0
	c = 0
	for i in range(0, n):
		l[i] = list(map(int, stdin.readline().split()))
	for j in range(0, n):
		for k in range(0, m):
			if l[j][k] < 0:
				l[j][k] = -1 * l[j][k]
				c += 1
			su += l[j][k]
			mi = min(mi, l[j][k])
	if c % 2 == 0:
		print(su)
	else:
		print(su - mi - mi)


for t in range(int(input())):
	(n, m) = map(int, input().split())
	schn = False
	schot = 0
	ms1 = []
	for k in range(n):
		ms = [int(i) for i in input().split()]
		for j in ms:
			if j == 0:
				schn = True
			elif j < 0:
				schot += 1
			ms1.append(abs(j))
	if schn:
		print(sum(ms1))
	elif schot % 2 == 0:
		print(sum(ms1))
	else:
		print(sum(ms1) - 2 * min(ms1))


t = int(input())
answers = []
for _ in range(t):
	minAbs = 101
	maxNegative = -100
	negativeCntr = 0
	zeroCntr = 0
	S = 0
	(n, m) = list(map(int, str(input()).split(' ')))
	for _ in range(n):
		nums = list(map(int, str(input()).split(' ')))
		for num in nums:
			if num < 0:
				negativeCntr += 1
			elif num == 0:
				zeroCntr += 1
			if abs(num) < minAbs:
				minAbs = abs(num)
			S += abs(num)
	if negativeCntr % 2 != 0 and zeroCntr % 2 == 0:
		S += -abs(minAbs) * 2
	answers.append(S)
for i in answers:
	print(i)


def get_max_sum(a):
	smallest_abs_value = -1
	sum_abs = 0
	count_neg_x = 0
	has_zero = False
	for row in a:
		for x in row:
			sum_abs += abs(x)
			if x < 0:
				count_neg_x += 1
			if smallest_abs_value < 0 or abs(x) < smallest_abs_value:
				smallest_abs_value = abs(x)
			if x == 0:
				has_zero = True
	if count_neg_x % 2 == 0 or has_zero:
		return sum_abs
	return sum_abs - 2 * smallest_abs_value
n_samples = int(input())
a = []
for t in range(n_samples):
	(n, m) = map(int, input().split(' '))
	for i in range(n):
		row = map(int, input().split(' '))
		a.append(row)
	print(get_max_sum(a))


for i in range(int(input())):
	(n, m) = map(int, input().split())
	suma = 0
	j = 0
	minx = 100000000000000000
	for i in range(n):
		a = list(map(int, input().split()))
		for k in range(m):
			suma += abs(a[k])
			if a[k] < 0:
				j += 1
			minx = min(minx, abs(a[k]))
	if j % 2 == 0:
		print(suma)
	else:
		print(suma - minx - minx)


t = int(input())
while t:
	(n, m) = map(int, input().split())
	mat = []
	for i in range(n):
		temp = list(map(int, input().split()))
		mat.append(temp)
	neg = 0
	summ = 0
	mini = float('inf')
	for i in range(n):
		for j in range(m):
			if mat[i][j] <= 0:
				neg += 1
			mini = min(mini, abs(mat[i][j]))
			summ += abs(mat[i][j])
	if neg % 2 == 0:
		print(summ)
	else:
		print(summ - mini * 2)
	t -= 1


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	b = []
	for j in range(n):
		b.append(list(map(int, input().split())))
	s = 0
	mi = float('inf')
	f = 0
	for w in range(n):
		for j in range(m):
			s += abs(b[w][j])
			if b[w][j] < 0:
				f += 1
			mi = min(mi, abs(b[w][j]))
	if f % 2 == 0:
		print(s)
	else:
		print(s - 2 * mi)


from typing import Counter
import sys
from collections import defaultdict as dd
from math import *

def vinp():
	return map(int, input().split())

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

def sinp():
	return input()

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

def mod(f):
	return f % 1000000007

def pr(*x):
	print(*x)

def finp():
	f = open('input.txt', 'r')
	f = f.read().split('\n')
	return f

def finp():
	f = open('input.txt', 'r')
	f = f.read().split('\n')
	return f

def fout():
	return open('output.txt', 'w')

def fpr(f, x):
	f.write(x + '\n')

def csort(c):
	sorted(c.items(), key=lambda pair: pair[1], reverse=True)

def indc(l, n):
	c = {}
	for i in range(n):
		c[l[i]] = c.get(l[i], []) + [i + 1]
	return c
cou = inp()
for i in range(cou):
	(n, m) = vinp()
	l = [linp() for i in range(n)]
	s = 0
	c = 0
	mx = sys.maxsize
	for i in range(n):
		for j in range(m):
			if l[i][j] < 0:
				c += 1
			s += abs(l[i][j])
			if abs(l[i][j]) < mx:
				mx = abs(l[i][j])
	if c % 2 != 0:
		pr(s - 2 * mx)
	else:
		pr(s)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	for _ in range(n):
		a.append(list(map(int, input().split())))
	s = 0
	x = 0
	val = 101
	for i in range(n):
		for j in range(m):
			s += abs(a[i][j])
			if a[i][j] < 0:
				x += 1
			val = min(val, abs(a[i][j]))
	if x % 2 != 0:
		s -= 2 * val
	print(s)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	X = 0
	M = 100
	Y = 0
	for i in range(n):
		for a in map(int, input().split()):
			if a < 0:
				X ^= 1
			M = min(M, abs(a))
			Y += abs(a)
	if X:
		print(Y - 2 * M)
	else:
		print(Y)


t = int(input())
(d, s1) = (0, [])
while d != t:
	(b, a) = ([], [])
	(n, m) = input().split()
	for i in range(int(n)):
		b = input().split()
		for j in range(int(m)):
			k = int(b[j])
			b[j] = k
		a += [b]
	(L1, L2, s, c) = ([], [], 0, 0)
	for i in range(int(n)):
		for j in range(int(m)):
			if a[i][j] < 0:
				c += 1
			s += abs(a[i][j])
			L2 += [a[i][j]]
		L1 += [L2]
		L2 = []
	if c % 2 == 0:
		s1 += [s]
	else:
		min1 = L1[0][0]
		for i in range(int(n)):
			for j in range(int(m)):
				if abs(L1[i][j]) <= abs(min1):
					min1 = L1[i][j]
					pos = [i, j]
		s1 += [s - 2 * abs(L1[pos[0]][pos[1]])]
	d += 1
for i in s1:
	print(i)


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


t = int(input().split()[0])
for _ in range(t):
	(r, c) = [int(i) for i in input().split()]
	sum = 0
	minabs = 200
	negs = 0
	for _ in range(r):
		aa = [int(i) for i in input().split()]
		for a in aa:
			sum += abs(a)
			minabs = min(minabs, abs(a))
			if a < 0:
				negs += 1
	if negs % 2 == 1:
		print(sum - 2 * minabs)
	else:
		print(sum)


from functools import cmp_to_key
from collections import deque
from heapq import heappush, heappop
from math import log, ceil
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def ii():
	return int(inp())

def li(lag=0):
	l = list(map(int, inp().split()))
	if lag != 0:
		for i in range(len(l)):
			l[i] += lag
	return l

def mi(n, lag=0):
	matrix = list()
	for i in range(n):
		matrix.append(li(lag))
	return matrix

def sli():
	return list(map(str, inp().split()))

def print_list(lista, space=' '):
	print(space.join(map(str, lista)))

class UnionFind:

	def __init__(self, n):
		self.parent = list(range(n))
		self.size = [1] * n
		self.num_sets = n

	def find(self, a):
		to_update = []
		while a != self.parent[a]:
			to_update.append(a)
			a = self.parent[a]
		for b in to_update:
			self.parent[b] = a
		return self.parent[a]

	def merge(self, a, b):
		a = self.find(a)
		b = self.find(b)
		if a == b:
			return
		if self.size[a] < self.size[b]:
			(a, b) = (b, a)
		self.num_sets -= 1
		self.parent[b] = a
		self.size[a] += self.size[b]

	def set_size(self, a):
		return self.size[self.find(a)]

	def __len__(self):
		return self.num_sets

def bisect_left(a, x):
	left = 0
	right = len(a)
	while left < right:
		mid = (left + right) // 2
		if a[mid] < x:
			left = mid + 1
		else:
			right = mid
	return left

def bisect_right(a, x):
	left = 0
	right = len(a)
	while left < right:
		mid = (left + right) // 2
		if a[mid] > x:
			right = mid
		else:
			left = mid + 1
	return left

def bisect_elements(a, x):
	return bisect_right(a, x) - bisect_left(a, x)

def custom_sort(lista):

	def cmp(x, y):
		if x + y > y + x:
			return 1
		else:
			return -1
	return sorted(lista, key=cmp_to_key(cmp))
MOD = 10 ** 9 + 7
maxN = 10 ** 5
FACT = [0] * maxN

def add(x, y):
	return (x + y) % MOD

def multiply(x, y):
	return x * y % MOD

def power(x, y):
	if y == 0:
		return 1
	elif y % 2:
		return multiply(x, power(x, y - 1))
	else:
		a = power(x, y // 2)
		return multiply(a, a)

def inverse(x):
	return power(x, MOD - 2)

def divide(x, y):
	return multiply(x, inverse(y))

def allFactorials():
	FACT[0] = 1
	for i in range(1, maxN):
		FACT[i] = multiply(i, FACT[i - 1])

def coeffBinom(n, k):
	if n < k:
		return 0
	return divide(FACT[n], multiply(FACT[k], FACT[n - k]))

def primes(N):
	smallest_prime = [1] * (N + 1)
	prime = []
	smallest_prime[0] = 0
	smallest_prime[1] = 0
	for i in range(2, N + 1):
		if smallest_prime[i] == 1:
			prime.append(i)
			smallest_prime[i] = i
		j = 0
		while j < len(prime) and i * prime[j] <= N:
			smallest_prime[i * prime[j]] = min(prime[j], smallest_prime[i])
			j += 1
	return (prime, smallest_prime)

def gcd(a, b):
	(s, t, r) = (0, 1, b)
	(old_s, old_t, old_r) = (1, 0, a)
	while r != 0:
		quotient = old_r // r
		(old_r, r) = (r, old_r - quotient * r)
		(old_s, s) = (s, old_s - quotient * s)
		(old_t, t) = (t, old_t - quotient * t)
	return (old_r, old_s, old_t)

def create_graph(n, m, undirected=1, unweighted=1):
	graph = [[] for i in range(n)]
	if unweighted:
		for i in range(m):
			[x, y] = li(lag=-1)
			graph[x].append(y)
			if undirected:
				graph[y].append(x)
	else:
		for i in range(m):
			[x, y, w] = li(lag=-1)
			w += 1
			graph[x].append([y, w])
			if undirected:
				graph[y].append([x, w])
	return graph

def create_tree(n, unweighted=1):
	children = [[] for i in range(n)]
	if unweighted:
		for i in range(n - 1):
			[x, y] = li(lag=-1)
			children[x].append(y)
			children[y].append(x)
	else:
		for i in range(n - 1):
			[x, y, w] = li(lag=-1)
			w += 1
			children[x].append([y, w])
			children[y].append([x, w])
	return children

def create_edges(m, unweighted=0):
	edges = list()
	if unweighted:
		for i in range(m):
			edges.append(li(lag=-1))
	else:
		for i in range(m):
			[x, y, w] = li(lag=-1)
			w += 1
			edges.append([w, x, y])
	return edges

def dist(tree, n, A, B=-1):
	s = [[A, 0]]
	(massimo, massimo_nodo) = (0, 0)
	distanza = -1
	v = [-1] * n
	while s:
		(el, dis) = s.pop()
		if dis > massimo:
			massimo = dis
			massimo_nodo = el
		if el == B:
			distanza = dis
		for child in tree[el]:
			if v[child] == -1:
				v[child] = 1
				s.append([child, dis + 1])
	return (massimo, massimo_nodo, distanza)

def diameter(tree):
	(_, foglia, _) = dist(tree, n, 0)
	(diam, _, _) = dist(tree, n, foglia)
	return diam

def dfs(graph, n, A):
	v = [-1] * n
	s = [[A, 0]]
	v[A] = 0
	while s:
		(el, dis) = s.pop()
		for child in graph[el]:
			if v[child] == -1:
				v[child] = dis + 1
				s.append([child, dis + 1])
	return v

def bfs(graph, n, A):
	v = [-1] * n
	s = deque()
	s.append([A, 0])
	v[A] = 0
	while s:
		(el, dis) = s.popleft()
		for child in graph[el]:
			if v[child] == -1:
				v[child] = dis + 1
				s.append([child, dis + 1])
	return v

def connected(graph, n):
	v = dfs(graph, n, 0)
	for el in v:
		if el == -1:
			return False
	return True

def topological(graph, n):
	indegree = [0] * n
	for el in range(n):
		for child in graph[el]:
			indegree[child] += 1
	s = deque()
	for el in range(n):
		if indegree[el] == 0:
			s.append(el)
	order = []
	while s:
		el = s.popleft()
		order.append(el)
		for child in graph[el]:
			indegree[child] -= 1
			if indegree[child] == 0:
				s.append(child)
	if n == len(order):
		return (False, order)
	else:
		return (True, [])

def bipartite(graph, n):
	color = [-1] * n
	color[0] = 0
	s = [0]
	while s:
		el = s.pop()
		for child in graph[el]:
			if color[child] == color[el]:
				return False
			if color[child] == -1:
				s.append(child)
			color[child] = 1 - color[el]
	return True

def dijkstra(graph, n, A):
	dist = [float('inf') for i in range(n)]
	prev = [-1 for i in range(n)]
	dist[A] = 0
	pq = []
	heappush(pq, [0, A])
	while pq:
		[d_v, v] = heappop(pq)
		if d_v != dist[v]:
			continue
		for (to, w) in graph[v]:
			if dist[v] + w < dist[to]:
				dist[to] = dist[v] + w
				prev[to] = v
				heappush(pq, [dist[to], to])
	return (dist, prev)

def dijkstra_0_1(graph, n, A):
	dist = [float('inf') for i in range(n)]
	dist[A] = 0
	p = deque()
	p.append(A)
	while p:
		v = p.popleft()
		for (to, w) in graph[v]:
			if dist[v] + w < dist[to]:
				dist[to] = dist[v] + w
			if w == 1:
				q.append(to)
			else:
				q.appendleft(to)
	return dist

def floyd_warshall(graph, n):
	dist = [[float('inf') for _ in range(n)] for _ in range(n)]
	for i in range(n):
		dist[i][i] = 0
		for (child, d) in graph[i]:
			dist[i][child] = d
			dist[child][i] = d
	for k in range(n):
		for i in range(n):
			for j in range(j):
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
	return dist

def minimum_spanning_tree(edges, n):
	edges = sorted(edges)
	union_find = UnionFind(n)
	used_edges = list()
	for (w, x, y) in edges:
		if union_find.find(x) != union_find.find(y):
			union_find.merge(x, y)
			used_edges.append([w, x, y])
	return used_edges

def parents_children_root_unrooted_tree(tree, n, root=0):
	q = deque()
	visited = [0] * n
	parent = [-1] * n
	children = [[] for i in range(n)]
	q.append(root)
	while q:
		all_done = 1
		visited[q[0]] = 1
		for child in tree[q[0]]:
			if not visited[child]:
				all_done = 0
				q.appendleft(child)
		if all_done:
			for child in tree[q[0]]:
				if parent[child] == -1:
					parent[q[0]] = child
					children[child].append(q[0])
			q.popleft()
	return (parent, children)

def all_longest_path_passing_from_node(parent, children, n):
	q = deque()
	visited = [len(children[i]) for i in range(n)]
	downwards = [[0, 0] for i in range(n)]
	upward = [1] * n
	longest_path = [1] * n
	for i in range(n):
		if not visited[i]:
			q.append(i)
			downwards[i] = [1, 0]
	while q:
		node = q.popleft()
		if parent[node] != -1:
			visited[parent[node]] -= 1
			if not visited[parent[node]]:
				q.append(parent[node])
		else:
			root = node
		for child in children[node]:
			downwards[node] = sorted([downwards[node][0], downwards[node][1], downwards[child][0] + 1], reverse=True)[0:2]
	s = [node]
	while s:
		node = s.pop()
		if parent[node] != -1:
			if downwards[parent[node]][0] == downwards[node][0] + 1:
				upward[node] = 1 + max(upward[parent[node]], downwards[parent[node]][1])
			else:
				upward[node] = 1 + max(upward[parent[node]], downwards[parent[node]][0])
		longest_path[node] = downwards[node][0] + downwards[node][1] + upward[node] - min([downwards[node][0], downwards[node][1], upward[node]]) - 1
		for child in children[node]:
			s.append(child)
	return longest_path

def finding_ancestors(parent, queries, n):
	steps = int(ceil(log(n, 2)))
	ancestors = [[-1 for i in range(n)] for j in range(steps)]
	ancestors[0] = parent
	for i in range(1, steps):
		for node in range(n):
			if ancestors[i - 1][node] != -1:
				ancestors[i][node] = ancestors[i - 1][ancestors[i - 1][node]]
	result = []
	for (node, k) in queries:
		ans = node
		if k >= n:
			ans = -1
		i = 0
		while k > 0 and ans != -1:
			if k % 2:
				ans = ancestors[i][ans]
			k = k // 2
			i += 1
		result.append(ans)
	return result

def prefix_sum(arr):
	r = [0] * (len(arr) + 1)
	for (i, el) in enumerate(arr):
		r[i + 1] = r[i] + el
	return r

def nearest_from_the_left_smaller_elements(arr):
	n = len(arr)
	res = [-1] * n
	s = []
	for (i, el) in enumerate(arr):
		while s and s[-1] >= el:
			s.pop()
		if s:
			res[i] = s[-1]
		s.append(el)
	return res

def sliding_window_minimum(arr, k):
	res = []
	q = deque()
	for (i, el) in enumerate(arr):
		while q and arr[q[-1]] >= el:
			q.pop()
		q.append(i)
		while q and q[0] <= i - k:
			q.popleft()
		if i >= k - 1:
			res.append(arr[q[0]])
	return res
t = ii()
for test in range(t):
	[n, m] = li()
	M = mi(n)
	neg = 0
	min_abs = 1000
	somma_abs = 0
	for i in range(n):
		for j in range(m):
			somma_abs += abs(M[i][j])
			if M[i][j] < 0:
				neg += 1
			min_abs = min(min_abs, abs(M[i][j]))
	if neg % 2 == 0:
		print(somma_abs)
	else:
		print(somma_abs - 2 * min_abs)


import math
a = int(input())
for i in range(a):
	(n, m) = map(int, input().split())
	ans = []
	total = 0
	ru = 0
	mini = math.inf
	for i in range(n):
		z = list(map(int, input().split()))
		for j in range(len(z)):
			if z[j] < 0:
				total += 1
			mini = min(mini, abs(z[j]))
			ru += abs(z[j])
	if total % 2 == 1:
		print(ru - 2 * mini)
	else:
		print(ru)


import os
from sys import stdin, stdout

def solve(tc):
	(n, m) = map(int, stdin.readline().split())
	mat = []
	for i in range(n):
		mat.append(list(map(int, stdin.readline().split())))
	zero = False
	minusCnt = 0
	mini = [-1, -1]
	minv = 101
	for i in range(n):
		for j in range(m):
			if mat[i][j] < 0:
				minusCnt += 1
			elif mat[i][j] == 0:
				zero = True
			if abs(mat[i][j]) < minv:
				minv = abs(mat[i][j])
				mini = [i, j]
	tot = 0
	if zero or minusCnt % 2 == 0:
		for i in range(n):
			for j in range(m):
				tot += abs(mat[i][j])
	else:
		for i in range(n):
			for j in range(m):
				if i == mini[0] and j == mini[1]:
					if mat[i][j] < 0:
						tot += mat[i][j]
					else:
						tot -= mat[i][j]
				else:
					tot += abs(mat[i][j])
	print(tot)
tcs = 1
tcs = int(stdin.readline().strip())
tc = 1
while tc <= tcs:
	solve(tc)
	tc += 1


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	(s, mi, count) = (0, 100, 0)
	for j in range(n):
		ma = list(map(int, input().split()))
		for k in ma:
			s += abs(k)
			if k < 0:
				count += 1
			mi = min(abs(k), mi)
	print(s - 2 * (count % 2) * mi)


import sys
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())
for _ in range(inp()):
	(n, m) = invr()
	a = []
	for _ in range(n):
		a.append(inlt())
	s = sum([sum(map(abs, x)) for x in a])
	i = sum([sum(map(lambda x: x < 0, y)) for y in a])
	if i % 2:
		m = min([min(map(abs, x)) for x in a])
		print(s - 2 * m)
	else:
		print(s)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = [[int(i) for i in input().split()] for j in range(n)]
	mini = 99999999999
	count = 0
	sum = 0
	for i in range(n):
		for j in range(m):
			if arr[i][j] < 0:
				count += 1
			mini = min(abs(arr[i][j]), mini)
			sum += abs(arr[i][j])
	if count % 2 != 0:
		print(sum - mini * 2)
	else:
		print(sum)


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


def numbersBox(matrix, n, m):
	minnum = float('+inf')
	numberOfNegative = 0
	numberOfZeros = 0
	totalsum = 0
	for i in range(n):
		for j in range(m):
			if abs(matrix[i][j]) < minnum:
				minnum = abs(matrix[i][j])
			if matrix[i][j] < 0:
				numberOfNegative += 1
			if matrix[i][j] == 0:
				numberOfZeros += 1
			totalsum += abs(matrix[i][j])
	if numberOfNegative % 2 == 0 or (numberOfNegative + numberOfZeros) % 2 == 0:
		print(totalsum)
	else:
		print(totalsum - 2 * minnum)
testcases = int(input())
while testcases:
	testcases -= 1
	(n, m) = list(map(int, input().split()))
	matrix = list()
	for i in range(n):
		matrix.append(list(map(int, input().split())))
	numbersBox(matrix, n, m)


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log2, ceil
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from bisect import insort
from collections import Counter
from collections import deque
from heapq import heappush, heappop, heapify
from itertools import permutations, combinations
from itertools import accumulate as ac
mod = int(1000000000.0) + 7
ip = lambda : int(stdin.readline())
inp = lambda : map(int, stdin.readline().split())
ips = lambda : stdin.readline().rstrip()
out = lambda x: stdout.write(str(x) + '\n')
t = ip()
for _ in range(t):
	(n, m) = inp()
	arr = []
	f = False
	for i in range(n):
		arr.append(list(inp()))
		if 0 in arr[i]:
			f = True
	ans = 0
	if f:
		for i in arr:
			for j in i:
				ans += abs(j)
	else:
		ct = 0
		minval = float('inf')
		for i in range(n):
			for j in range(m):
				minval = min(minval, abs(arr[i][j]))
				if arr[i][j] < 0:
					ct += 1
		if ct % 2 == 0:
			for i in arr:
				for j in i:
					ans += abs(j)
		else:
			pos = []
			cur = 0
			for i in range(n):
				for j in range(m):
					cur += abs(arr[i][j])
					if abs(arr[i][j]) == minval:
						pos.append((i, j))
			ans = []
			for i in pos:
				(x, y) = i
				val = cur
				val -= abs(arr[x][y])
				val += -abs(arr[x][y])
				ans.append(val)
			ans = min(ans)
	print(ans)


import sys
import math
from collections import Counter
from collections import OrderedDict
from collections import defaultdict
from functools import reduce
sys.setrecursionlimit(10 ** 6)

def inputt():
	return sys.stdin.readline().strip()

def printt(n):
	sys.stdout.write(str(n) + '\n')

def listt():
	return [int(i) for i in inputt().split()]

def gcd(a, b):
	return math.gcd(a, b)

def lcm(a, b):
	return a * b // gcd(a, b)

def factors(n):
	step = 2 if n % 2 else 1
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(math.sqrt(n)) + 1, step) if n % i == 0)))

def comb(n, k):
	factn = math.factorial(n)
	factk = math.factorial(k)
	fact = math.factorial(n - k)
	ans = factn // (factk * fact)
	return ans

def is_prime(n):
	if n <= 1:
		return False
	if n == 2:
		return True
	if n > 2 and n % 2 == 0:
		return False
	max_div = math.floor(math.sqrt(n))
	for i in range(3, 1 + max_div, 2):
		if n % i == 0:
			return False
	return True

def maxpower(n, x):
	B_max = int(math.log(n, x)) + 1
	return B_max
t = int(input())
for _ in range(t):
	(n, m) = map(int, inputt().split())
	l = []
	count = 0
	mini = 1001
	for i in range(n):
		li = listt()
		l.append(li)
	summ = 0
	for i in range(n):
		for j in range(m):
			if mini > abs(l[i][j]):
				mini = abs(l[i][j])
			summ += abs(l[i][j])
			if l[i][j] < 0:
				count += 1
	if count % 2 == 0:
		print(summ)
	else:
		print(summ - 2 * mini)


import sys, os.path
from collections import *
from heapq import *
from copy import *
import math
mod = 10 ** 9 + 7
read = lambda : map(int, input().split())
inf = sys.maxsize
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
for t in range(int(input())):
	(n, m) = read()
	mat = []
	for i in range(n):
		l = list(read())
		mat.append(l)
	cnt = 0
	minn = inf
	ans = 0
	for i in range(n):
		for j in range(m):
			if mat[i][j] < 0:
				cnt += 1
			ans += abs(mat[i][j])
			minn = min(minn, abs(mat[i][j]))
	if cnt % 2 == 0:
		print(ans)
	else:
		print(ans - 2 * minn)


T = int(input())
for t in range(T):
	(x, y) = map(int, input().split())
	negatives = 0
	total_sum = 0
	min_negative = 1000
	for X in range(x):
		i = map(int, input().split())
		for I in i:
			total_sum += abs(I)
			min_negative = min(min_negative, abs(I))
			if I <= 0:
				negatives += 1
	ans = 0
	if negatives % 2 == 0:
		ans = total_sum
	else:
		ans = total_sum - 2 * min_negative
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	som = 0
	minus = 0
	minm = 10 ** 18
	mat = []
	for i in range(n):
		arr = list(map(int, input().split()))
		mat.append(arr)
	for i in range(n):
		for j in range(m):
			if mat[i][j] < 0:
				minus += 1
			minm = min(abs(mat[i][j]), minm)
			som += abs(mat[i][j])
	if minus % 2 == 0:
		print(som)
	else:
		print(som - 2 * minm)


t = int(input())
fields = []
for i in range(t):
	(n, m) = list(map(int, input().split()))
	field = []
	for j in range(n):
		field.append(list(map(int, input().split())))
	fields.append(field)
results = []
for i in range(t):
	negatives = 0
	s = 0
	for x in fields[i]:
		for y in x:
			if y <= 0:
				negatives += 1
			s += abs(y)
	negatives %= 2
	if negatives:
		m = abs(fields[i][0][0])
		for x in fields[i]:
			for y in x:
				n = abs(y)
				if n < m:
					m = n
		s -= m * 2
	print(s)


import math

def gridPrint(a):
	return '\n'.join([' '.join([str(a[i][j]) for j in range(m)]) for i in range(n)])

def solve(n, m, a):
	trash = math.inf
	for i in range(n):
		for j in range(m):
			trash = min(trash, abs(a[i][j]))
	negatives = 0
	for i in range(n):
		for j in range(m):
			if a[i][j] < 0:
				negatives += 1
	sm = 0
	for i in range(n):
		for j in range(m):
			sm += abs(a[i][j])
	sm -= trash
	if negatives % 2 == 1:
		trash *= -1
	return sm + trash
t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	grid = []
	for _ in range(n):
		grid.append(list(map(int, input().split())))
	print(solve(n, m, grid))


t = int(input())
for case in range(t):
	(n, m) = [int(x) for x in input().split(' ')]
	grid = []
	for i in range(n):
		grid += [int(x) for x in input().split(' ')]
	grid_abs = [abs(x) for x in grid]
	grid_abs.sort()
	if 0 in grid:
		ans = sum(grid_abs)
	else:
		ans = sum(grid_abs)
		negs = len([x for x in grid if x < 0]) % 2
		ans -= grid_abs[0] * 2 * negs
	print(ans)


from sys import stdin
input = stdin.readline
from collections import defaultdict
for _ in range(int(input())):
	(r, c) = map(int, input().split())
	arr = []
	for i in range(r):
		arr.append(list(map(int, input().split())))
	neg = 0
	su = 0
	mini = float('inf')
	for i in range(r):
		for j in range(c):
			su += abs(arr[i][j])
			if arr[i][j] < 0:
				neg += 1
			mini = min(mini, abs(arr[i][j]))
	if neg % 2 == 0:
		print(su)
	else:
		print(su - 2 * mini)


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


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	x = 0
	mn = None
	sm = 0
	for __ in range(n):
		s = list(map(int, input().split()))
		for i in s:
			if mn is None or abs(i) < mn:
				mn = abs(i)
			if i <= 0:
				x += 1
			sm += abs(i)
	if x % 2 == 0:
		print(sm)
	else:
		print(sm - 2 * mn)


t = int(input())
while t > 0:
	t -= 1
	(n, m) = map(int, input().split())
	res = []
	mi = 1000000000000000000
	(c1, c2, sum) = (0, 0, 0)
	for i in range(n):
		l = list(map(int, input().split()))
		res.append(l)
	for i in range(n):
		for j in range(m):
			if res[i][j] < 0:
				c2 += 1
			sum += abs(res[i][j])
			mi = min(abs(res[i][j]), mi)
	if c2 % 2 == 0:
		print(sum)
	else:
		print(sum - 2 * mi)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [[-1 for z in range(m)] for y in range(n)]
	for z in range(n):
		a[z] = list(map(int, input().split()))
	mc = 0
	minv = 10 ** 20
	ts = 0
	for z in range(n):
		for y in range(m):
			if a[z][y] < 0:
				mc += 1
			ts += abs(a[z][y])
			minv = min(minv, abs(a[z][y]))
	if mc % 2 == 0:
		print(ts)
	else:
		print(ts - 2 * minv)


import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
	(n, m) = map(int, input().split())
	A = []
	for i in range(n):
		A.append(list(map(int, input().split())))
	no = 0
	mv = 10 ** 9
	s = 0
	for i in range(n):
		for j in range(m):
			if A[i][j] < 0:
				no = no + 1
			mv = min(mv, abs(A[i][j]))
			s = s + abs(A[i][j])
	if no % 2 != 0:
		s = s - mv - mv
	print(s)


def numbers_box():
	t = int(input())
	for _ in range(t):
		(n, m) = [int(x) for x in input().split(' ')]
		sum_all_elems = 0
		min_elem = 1000
		minus = 0
		for i in range(n):
			for x in input().split(' '):
				if int(x) < 0:
					minus += 1
				sum_all_elems += abs(int(x))
				min_elem = min(min_elem, abs(int(x)))
		if minus % 2 != 0:
			sum_all_elems = sum_all_elems - 2 * min_elem
		print(sum_all_elems)
numbers_box()


import sys
import collections as cc
import itertools as it
import math as mt
import functools as ft
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
for tc in range(int(input())):
	(n, m) = I()
	ar = [I() for i in range(n)]
	ct = 0
	su = 0
	mi = mt.inf
	for i in range(n):
		for j in range(m):
			mi = min(abs(ar[i][j]), mi)
			su += abs(ar[i][j])
			if ar[i][j] < 0:
				ct += 1
	if ct % 2 == 0:
		print(abs(su))
	else:
		print(su - 2 * mi)


test = int(input())
while test > 0:
	(n, m) = map(int, input().split())
	mat = []
	for i in range(n):
		l = list(map(int, input().split()))
		mat.append(l)
	z = 0
	neg = []
	sum1 = 0
	mini = 101
	for i in range(n):
		for j in range(m):
			k = mat[i][j]
			if k == 0:
				z += 1
			elif k < 0:
				neg.append(k)
			mini = min(mini, abs(k))
			sum1 += abs(k)
	if len(neg) > 0:
		if z > 0:
			print(sum1)
		elif len(neg) % 2 == 0:
			print(sum1)
		else:
			print(sum1 - 2 * mini)
	else:
		print(sum1)
	test -= 1


from math import *
from sys import *
t = int(stdin.readline())
for _ in range(t):
	(n, k) = map(int, stdin.readline().split())
	m = []
	for i in range(n):
		a = list(map(int, stdin.readline().split()))
		m.append(a)
	x = 0
	mn = 101
	sm = 0
	for i in range(n):
		for j in range(k):
			if m[i][j] < 0:
				x += 1
			if abs(m[i][j]) < mn:
				mn = abs(m[i][j])
			sm += abs(m[i][j])
	if x % 2 == 0:
		print(sm)
	else:
		print(sm - 2 * mn)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		ls = list(map(int, input().split()))
		l.append(ls)
	count = 0
	ans = 0
	minimum = 101
	for i in range(n):
		for j in range(m):
			x = l[i][j]
			if x < 0:
				count += 1
			minimum = min(minimum, abs(x))
			ans += abs(x)
	if count % 2 == 0:
		print(ans)
	else:
		print(ans - (minimum + minimum))


for _ in range(int(input())):
	mat = []
	(n, m) = map(int, input().split())
	neg = 0
	mn = 9999999
	res = 0
	for i in range(n):
		tmp = list(map(int, input().split()))
		mat.append(tmp)
	for i in range(n):
		for j in range(m):
			if mat[i][j] < 0:
				neg += 1
			mn = min(mn, abs(mat[i][j]))
			res += abs(mat[i][j])
	if neg % 2 != 0:
		res -= 2 * mn
	print(res)


R = lambda : map(int, input().split())
(t,) = R()
for _ in [0] * t:
	(n, m) = R()
	a = []
	f = 0
	for _ in [0] * n:
		for x in R():
			a += (abs(x),)
			f ^= x < 0
	print(sum(a) - 2 * min(a) * f)


total = int(input())
for i in range(total):
	input_list = input().split()
	n = int(input_list[0])
	m = int(input_list[1])
	Grid = [[0 for x in range(m)] for y in range(n)]
	for i in range(n):
		input_grid = input().split()
		for j in range(m):
			Grid[i][j] = int(input_grid[j])
	count = 0
	sum = 0
	for i in range(n):
		for j in range(m):
			if Grid[i][j] < 0:
				count += 1
	if count % 2 == 0:
		for i in range(n):
			for j in range(m):
				sum += abs(Grid[i][j])
		print(sum)
	else:
		min = abs(Grid[0][0])
		for i in range(n):
			for j in range(m):
				sum += abs(Grid[i][j])
				if abs(Grid[i][j]) < min:
					min = abs(Grid[i][j])
		print(sum - 2 * min)


def maximize_sum(matrix):
	negative = [x for x in matrix if x < 0]
	positive = [x for x in matrix if x >= 0]
	negative.sort()
	positive.sort()
	if len(positive) > 0:
		if positive[0] == 0:
			return sum(positive) + sum(list(map(lambda x: x * -1, negative)))
	if len(negative) % 2 == 0:
		return sum(positive) + sum(list(map(lambda x: x * -1, negative)))
	else:
		dup_negative = list(map(lambda x: x * -1, negative))
		if len(positive) > 0:
			if dup_negative[-1] > positive[0]:
				return sum(dup_negative) + sum(positive[1:]) - positive[0]
			else:
				return sum(dup_negative[:-1]) + sum(positive) - dup_negative[-1]
		else:
			return sum(dup_negative[:-1]) - dup_negative[-1]
test = int(input())
for x in range(test):
	(m, n) = list(map(int, input().split()))
	matrix = []
	for y in range(m):
		matrix.extend(list(map(int, input().split())))
	print(maximize_sum(matrix))


from collections import Counter
from collections import OrderedDict
from collections import defaultdict
import bisect
import math
from sys import setrecursionlimit

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def fre_count(mylist):
	return Counter(mylist)
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	grid = [[int(x) for x in input().split()] for x in range(n)]
	total = 0
	count = 0
	mini = float('inf')
	for i in range(n):
		for j in range(m):
			total += abs(grid[i][j])
			if grid[i][j] < 0:
				count += 1
			mini = min(mini, abs(grid[i][j]))
	if count % 2 != 0:
		print(total - mini * 2)
	else:
		print(total)


for t in range(int(input())):
	(n, m) = map(int, input().split())
	arr = []
	minm = 999999999999
	ans = 0
	for i in range(n):
		arr.append([int(x) for x in input().split()])
	count = 0
	for i in range(n):
		for j in range(m):
			ans += abs(arr[i][j])
			if arr[i][j] < 0:
				count += 1
			minm = min(abs(arr[i][j]), minm)
	if count % 2 == 0:
		print(ans)
	else:
		print(ans - 2 * minm)


def maxSum(arr, r):
	(isZeroPresentInGrid, cntOFNegatives, ans) = (False, 0, 0)
	smallestNum = 101
	for i in range(r):
		for num in arr[i]:
			if num < 0:
				cntOFNegatives += 1
			elif num == 0:
				isZeroPresentInGrid = True
			ans += abs(num)
			smallestNum = min(smallestNum, abs(num))
	if isZeroPresentInGrid or cntOFNegatives % 2 == 0:
		return ans
	return ans - smallestNum * 2
t = int(input())
while t:
	(r, c) = map(int, input().split(' '))
	arr = []
	for i in range(r):
		row = list(map(int, input().split(' ')))
		arr.append(row)
	print(maxSum(arr, r))
	t -= 1


for _ in range(int(input())):
	(m, n) = map(int, input().split())
	ls = []
	for i in range(m):
		ls.append(list(map(int, input().split())))
	ls0 = []
	lsx = []
	t = 0
	s = 0
	for j in range(m):
		for k in range(n):
			if ls[j][k] < 0:
				t += 1
				ls0.append(ls[j][k])
			else:
				lsx.append(ls[j][k])
	if t % 2 == 0:
		print(sum(lsx) - sum(ls0))
	else:
		ls0.sort()
		lsx.sort()
		if len(lsx) == 0:
			print(-sum(ls0) + 2 * ls0[-1])
		elif ls0[-1] * -1 > lsx[0]:
			print(sum(lsx) - sum(ls0) - 2 * lsx[0])
		else:
			print(sum(lsx) - sum(ls0) + 2 * ls0[-1])


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	for x in range(n):
		a += [int(x) for x in input().split()]
	neg_count = 0
	for x in a:
		if x < 0:
			neg_count += 1
	if 0 in a or neg_count % 2 == 0:
		print(sum(map(abs, a)))
	else:
		mn = 10 ** 10
		mn = min(map(abs, a))
		print(sum(map(abs, a)) - 2 * mn)


for w in range(int(input())):
	(n, m) = tuple(map(int, input().split()))
	a = []
	l = []
	ans = 0
	x = 0
	for i in range(n):
		a.append(list(map(int, input().split())))
	for i in range(n):
		y = 0
		for j in range(m):
			ans += abs(a[i][j])
			l.append(abs(a[i][j]))
			if a[i][j] <= 0:
				y += 1
		x += y % 2
	x1 = x % 2
	if x1 == 0:
		print(ans)
	else:
		print(ans - 2 * min(l))


T = int(input())
for case in range(T):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		a += list(map(int, input().split()))
	minimum = 100
	negative = 0
	total = 0
	for i in a:
		if i < 0:
			negative += 1
			i = -1 * i
		total += i
		minimum = min(minimum, i)
	if negative % 2 == 1:
		print(total - 2 * minimum)
	else:
		print(total)


import sys
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	grid = []
	for _ in range(n):
		temp = list(map(int, input().split()))
		grid.append(temp)
	neg = 0
	tot = 0
	mini = sys.maxsize
	for i in range(n):
		for j in range(m):
			if grid[i][j] < 0:
				neg += 1
			mini = min(mini, abs(grid[i][j]))
			tot += abs(grid[i][j])
	if neg % 2 == 0:
		print(tot)
	else:
		print(tot - 2 * mini)


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


ans = []

def main():
	(n, m) = list(map(int, input().split()))
	minval = 101
	sumval = 0
	count = 0
	for _ in range(n):
		listt = list(map(int, input().split()))
		for i in listt:
			if i < 0:
				minval = min(minval, -i)
				sumval += -i
				count += 1
			else:
				minval = min(minval, i)
				sumval += i
	if count % 2:
		ans.append(str(sumval - 2 * minval))
	else:
		ans.append(str(sumval))
for _ in range(int(input())):
	main()
print('\n'.join(ans))


def put(x):
	count[0] += int(x <= 0)
	return abs(x)
t = int(input())
for j in range(t):
	(m, n) = map(int, input().split())
	count = [0]
	a = []
	for i in range(m):
		a += [put(int(r)) for r in input().split()]
	a.sort()
	result = sum(a) - 2 * (count[0] % 2) * a[0]
	print(result)


t = int(input())

def solve():
	(n, m) = map(int, input().split())
	grid = []
	for i in range(n):
		grid.append(list(map(int, input().split())))
	pos = 0
	neg = 0
	for i in grid:
		for j in i:
			if j > 0:
				pos += 1
			else:
				neg += 1
	pos += int(neg / 2) * 2
	pos = int(pos)
	lst = []
	for i in grid:
		for j in i:
			lst.append(abs(j))
	lst.sort()
	lst.reverse()
	ans = 0
	for i in range(pos):
		ans += lst[i]
	for i in range(pos, len(lst)):
		ans -= lst[i]
	print(ans)
for i in range(t):
	solve()


t = int(input())
for i in range(t):
	(n, m) = [int(item) for item in input().split(' ')]
	numbers = []
	for j in range(n):
		numbers.append([int(item) for item in input().split(' ')])
	numbers = [item for sublist in numbers for item in sublist]
	numbers_abs = [abs(item) for item in numbers]
	total = 0
	if 0 in numbers:
		total = sum(numbers_abs)
	else:
		count_neg = 0
		for item in numbers:
			if item < 0:
				count_neg += 1
		if count_neg % 2 == 0:
			total = sum(numbers_abs)
		else:
			total = sum(numbers_abs) - 2 * min(numbers_abs)
	print(total)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		s = list(map(int, input().split()))
		l.append(s)
	mn = float('inf')
	s = 0
	neg = 0
	for i in range(n):
		for j in range(m):
			s += abs(l[i][j])
			mn = min(mn, abs(l[i][j]))
			if l[i][j] <= 0:
				neg += 1
	if neg % 2 != 0:
		s -= 2 * mn
	print(s)


def ass(a, b):
	if a != b:
		print(f'Assertion error: {a} != {b}')
	else:
		print('OK')

def number():
	return int(input())

def numbers():
	return [int(item) for item in input().split()]

def word():
	return input()

def words():
	return [item for item in input().split()]

def dump(lst):
	for (i, item) in enumerate(lst):
		print(i, item)

def binsearch(arr, a, b):
	m = (a + b) // 2
	if a >= b:
		return a - 1 if arr[a] == 0 else a
	return binsearch(arr, a, m - 1) if arr[m] == 0 else binsearch(arr, m + 1, b)

def f(arr):
	arr = [item for sublist in arr for item in sublist]
	neg = 0
	pos = 0
	zero = 0
	summa = 0
	smallest = abs(arr[0])
	for item in arr:
		if item < 0:
			neg += 1
		elif item == 0:
			zero += 1
		else:
			pos += 1
		summa += abs(item)
		if abs(item) < smallest:
			smallest = abs(item)
	if neg % 2 == 0:
		return summa
	else:
		return summa if zero > 0 else summa - 2 * smallest
for t in range(number()):
	(n, m) = numbers()
	arr = [numbers() for i in range(n)]
	print(f(arr))


def read_int():
	n = int(input())
	return n

def read_ints():
	ints = [int(x) for x in input().split(' ')]
	return ints

def solve(n, m, a):
	ncount = 0
	total = 0
	gmin = None
	zero = False
	for i in range(n):
		row = a[i]
		if 0 in row:
			zero = True
		for val in row:
			if val < 0:
				ncount += 1
			total += abs(val)
			if gmin is None:
				gmin = abs(val)
			else:
				gmin = min(gmin, abs(val))
	if zero:
		return total
	if ncount % 2 == 0:
		return total
	else:
		return total - 2 * gmin
t = read_int()
for case in range(t):
	(n, m) = read_ints()
	a = []
	for _ in range(n):
		a.append(read_ints())
	sol = solve(n, m, a)
	print(sol)


from sys import stdin
for _ in range(int(stdin.readline())):
	(n, m) = map(int, stdin.readline().split())
	maps = []
	ans = 0
	lowest = float('inf')
	negcount = 0
	zero = 0
	for i in range(n):
		cur = list(map(int, stdin.readline().split()))
		for j in range(m):
			x = cur[j]
			if x < 0:
				negcount += 1
			elif x == 0:
				zero += 1
			lowest = min(abs(lowest), abs(x))
			ans += abs(x)
	if (zero + negcount) % 2 == 0:
		print(ans)
	elif negcount % 2 == 0:
		print(ans)
	elif negcount % 2 == 1:
		print(ans - 2 * lowest)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	c = 0
	s = 0
	mn = 10001
	for i in range(n):
		x = list(map(int, input().split()))
		for j in range(m):
			s += abs(x[j])
			if mn > abs(x[j]):
				mn = abs(x[j])
			if x[j] < 0:
				c += 1
	if c % 2 == 0 or mn == 0:
		print(s)
	else:
		print(s - 2 * mn)


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


t = int(input())
res = []
for i in range(t):
	(n, m) = map(int, input().split())
	x = 0
	c = 0
	mi = 101
	for j in range(n):
		a = list(map(int, input().split()))
		for k in range(m):
			if a[k] < 0:
				c += 1
			if abs(a[k]) < mi:
				mi = abs(a[k])
			x += abs(a[k])
	if c % 2 == 0:
		res.append(x)
	else:
		res.append(x - 2 * mi)
for i in res:
	print(i)


tests = int(input())
for test in range(tests):
	(n, m) = map(int, input().split())
	minAbs = None
	cntMinus = 0
	s = 0
	for i in range(n):
		for v in map(int, input().split()):
			va = abs(v)
			s += va
			if minAbs == None or minAbs > va:
				minAbs = va
			if v < 0:
				cntMinus += 1
	if cntMinus % 2 == 1:
		s -= 2 * minAbs
	print(s)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(n):
		arr1 = list(map(int, input().split()))
		arr.append(arr1)
	count = 0
	sum1 = 0
	arr1 = []
	for i in range(n):
		for j in range(m):
			sum1 += abs(arr[i][j])
			arr1.append(abs(arr[i][j]))
			if arr[i][j] <= 0:
				count += 1
	if count % 2 == 0:
		print(sum1)
	else:
		a = sorted(arr1)
		a[0] = -a[0]
		print(sum(a))


for _ in range(int(input())):
	(r, c) = map(int, input().split())
	(ans, d, neg, min) = (0, 0, 0, 101)
	for i in range(r):
		l = [int(k) for k in input().split()]
		for j in range(c):
			if l[j] == 0:
				d = 1
			elif l[j] < 0:
				neg += 1
			ans += abs(l[j])
			if abs(l[j]) < min:
				min = abs(l[j])
	if d == 1 or neg % 2 == 0:
		print(ans)
	else:
		print(ans - 2 * min)


t = int(input())
for i in range(0, t):
	a = []
	(n, m) = map(int, input().split())
	k = 0
	min_mod = 'str'
	for j in range(0, n):
		a.append(list(map(int, input().split())))
		if min_mod == 'str':
			min_mod = abs(a[-1][0])
		for h in range(0, m):
			if a[-1][h] < 0:
				k += 1
			if abs(a[-1][h]) < min_mod:
				min_mod = abs(a[-1][h])
	s = 0
	for q in range(0, n):
		for w in range(0, m):
			s += abs(a[q][w])
	if k % 2 == 0:
		print(s)
	else:
		print(s - min_mod * 2)


import sys

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

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for k in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for k in range(c)] for k in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** (-10)
for _ in range(INT()):
	(H, W) = MAP()
	grid = [[]] * H
	for i in range(H):
		grid[i] = LIST()
	mcnt = 0
	mn = INF
	zero = 0
	ans = 0
	for i in range(H):
		for j in range(W):
			if grid[i][j] == 0:
				zero += 1
			elif grid[i][j] < 0:
				mcnt += 1
			mn = min(mn, abs(grid[i][j]))
			ans += abs(grid[i][j])
	if mcnt % 2 == 1 and (not zero):
		ans -= mn * 2
	print(ans)


from sys import stdin, stdout
from collections import *
from math import *
st = lambda : list(stdin.readline().strip())
li = lambda : list(map(int, stdin.readline().split()))
mp = lambda : map(int, stdin.readline().split())
inp = lambda : int(stdin.readline())
pr = lambda n: stdout.write(str(n) + '\n')
mod = 1000000007
INF = float('inf')

def solve():
	(n, m) = mp()
	l = [li() for i in range(n)]
	ma = INF
	s = 0
	c = 0
	for i in l:
		for j in i:
			s += abs(j)
			if j < 0:
				c += 1
			ma = min(ma, abs(j))
	if c % 2 == 0:
		pr(s)
	else:
		pr(s - 2 * ma)
for _ in range(inp()):
	solve()


ii = int(input())
for i in range(ii):
	(a, b) = input().split()
	sum_all = 0
	min_el = 1000
	kol_vo_null = 0
	kol_vo_otr = 0
	for k in range(int(a)):
		s = input().split()
		for kk in s:
			sum_all = sum_all + abs(int(kk))
			if int(kk) == 0:
				kol_vo_null = kol_vo_null + 1
			elif int(kk) < 0:
				kol_vo_otr = kol_vo_otr + 1
			if min_el >= abs(int(kk)):
				min_el = abs(int(kk))
	if kol_vo_otr == 0 or kol_vo_otr % 2 == 0 or kol_vo_null > 0:
		print(sum_all)
	else:
		print(sum_all - 2 * min_el)


t = int(input())
for _ in range(t):
	nm = list(map(int, input().split()))
	n = nm[0]
	numbers = []
	for _ in range(n):
		data = list(map(int, input().split()))
		numbers += data
	neg = 0
	zero = 0
	for i in numbers:
		if i < 0:
			neg += 1
		elif i == 0:
			zero += 1
	if neg % 2 == 0 or zero > 0:
		numbers = list(map(abs, numbers))
		result = sum(numbers)
	else:
		numbers = list(map(abs, numbers))
		minimum = min(numbers)
		result = sum(numbers) - 2 * minimum
	print(result)


tcs = int(input())
for _ in range(tcs):
	(r, c) = map(int, input().split(' '))
	negcnt = 0
	minpos = 1000000000
	maxneg = -1000000000
	sumpos = 0
	sumneg = 0
	for i in range(r):
		tmp = list(map(int, input().split(' ')))
		for j in range(c):
			a = tmp[j]
			if a < 0:
				negcnt += 1
				maxneg = max(maxneg, a)
				sumneg += a
			else:
				minpos = min(minpos, a)
				sumpos += a
	if negcnt % 2 == 0:
		print(sumpos - sumneg)
	elif minpos < -maxneg:
		print(sumpos - sumneg - 2 * minpos)
	else:
		print(sumpos - sumneg + 2 * maxneg)


T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	g = [list(map(int, input().split())) for _ in range(N)]
	c = sum([sum([int(n < 0) for n in g[i]]) for i in range(N)])
	S = sum([sum([abs(n) for n in g[i]]) for i in range(N)])
	M = min([min([abs(n) for n in g[i]]) for i in range(N)])
	if ~c & 1:
		print(S)
	else:
		print(S - 2 * abs(M))


import collections
import math
import collections
import sys
from functools import reduce
import decimal
sys.setrecursionlimit(10 ** 9)
decimal.getcontext().rounding = decimal.ROUND_HALF_UP
graphDict = collections.defaultdict
queue = collections.deque()

class Graphs:

	def __init__(self):
		self.graph = graphDict(list)

	def add_edge(self, u, v):
		self.graph[u].append(v)

	def dfs_utility(self, nodes, visited_nodes):
		visited_nodes.add(nodes)
		for neighbour in self.graph[nodes]:
			if neighbour not in visited_nodes:
				self.dfs_utility(neighbour, visited_nodes)
			else:
				return neighbour

	def dfs(self, node):
		Visited = set()
		self.dfs_utility(node, Visited)

	def bfs(self, node):
		visited = set()
		if node not in visited:
			queue.append(node)
			visited.add(node)
		while queue:
			parent = queue.popleft()
			print(parent)
			for item in self.graph[parent]:
				if item not in visited:
					queue.append(item)
					visited.add(item)

def rounding(n):
	return int(decimal.Decimal(f'{n}').to_integral_value())

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def inp():
	return sys.stdin.readline().strip()

def map_inp(v_type):
	return map(v_type, inp().split())

def list_inp(v_type):
	return list(map_inp(v_type))
for _ in range(int(inp())):
	(n, m) = map_inp(int)
	arr = []
	for i in range(n):
		arr.append(list_inp(int))
	positive = []
	negative = []
	zero = []
	for i in range(n):
		for j in range(m):
			if arr[i][j] > 0:
				positive.append(arr[i][j])
			elif arr[i][j] < 0:
				negative.append(arr[i][j])
			else:
				zero.append(arr[i][j])
	total = [-item for item in negative] + list.copy(positive)
	total.sort()
	if len(negative) & 1 == 0 or len(zero) > 0:
		print(sum(total))
	else:
		ans = 0
		for i in range(len(total)):
			if i == 0:
				ans -= total[i]
			else:
				ans += total[i]
		print(ans)


from sys import *
from collections import defaultdict as dd
from math import *
from bisect import *

def sinp():
	return input()

def inp():
	return int(sinp())

def minp():
	return map(int, sinp().split())

def linp():
	return list(minp())

def strl():
	return list(sinp())

def pr(x):
	print(x)
mod = int(1000000000.0 + 7)
for _ in range(inp()):
	(n, m) = minp()
	mat = []
	for i in range(n):
		mat.extend(linp())
	neg = 0
	res = 0
	for i in mat:
		if i < 0:
			neg += 1
		res += abs(i)
	if neg & 1:
		num = maxsize
		for i in mat:
			num = min(num, abs(i))
		res -= 2 * num
	pr(res)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	k = []
	co = 0
	c = 0
	for i in range(n):
		x = list(map(int, input().split()))
		l.append(x)
	b = min(l[0])
	c1 = 9999999999
	for v in l:
		co = co + v.count(0)
	for j in range(len(l)):
		for i in range(len(l[j])):
			if l[j][i] < 0:
				l[j][i] = abs(l[j][i])
				c = c + 1
		k.append(sum(l[j]))
	for x in l:
		c1 = min(c1, min(x))
	if c % 2 == 0:
		print(sum(k))
	elif co > 0 and c % 2 == 1:
		print(sum(k))
	else:
		print(sum(k) - 2 * c1)


n = int(input())
for k in range(n):
	temp = 100
	count = 0
	total = 0
	neg = 0
	(a, b) = map(int, input().split())
	for i in range(a):
		list = [int(x) for x in input().split()]
		for j in range(b):
			temp = min(temp, abs(list[j]))
			if list[j] <= 0:
				count += 1
				neg += list[j]
			else:
				total += list[j]
	print(neg * -1 + total) if count % 2 == 0 else print(neg * -1 + total - temp * 2)


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


import io
import os
from collections import Counter, defaultdict, deque

def solve(R, C, grid):
	neg = []
	pos = []
	for r in range(R):
		for c in range(C):
			x = grid[r][c]
			if x >= 0:
				pos.append(x)
			else:
				neg.append(x)
	neg.sort()
	pos.sort(reverse=True)
	if len(neg) % 2 == 0:
		return -sum(neg) + sum(pos)
	else:
		x = neg.pop()
		y = 0
		if pos:
			y = pos.pop()
			if abs(x) > abs(y):
				x *= -1
				y *= -1
		return -sum(neg) + x + y + sum(pos)
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
TC = int(input())
for tc in range(1, TC + 1):
	(N, M) = [int(x) for x in input().split()]
	grid = [[int(x) for x in input().split()] for i in range(N)]
	ans = solve(N, M, grid)
	print(ans)


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


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		a.append(list(map(int, input().split())))
	smallest = 100000000
	neg = 0
	ans = 0
	for i in range(n):
		for j in range(m):
			ans += abs(a[i][j])
			if abs(a[i][j]) < smallest:
				smallest = abs(a[i][j])
			if a[i][j] <= 0:
				neg += 1
	if neg % 2:
		print(ans - 2 * smallest)
	else:
		print(ans)


t = int(input())
for z in range(t):
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	countneg = 0
	mini = 999
	sum = 0
	for i in range(n):
		row = input().split()
		for j in range(m):
			row[j] = int(row[j])
			if row[j] < 0:
				countneg += 1
			if mini > abs(row[j]):
				mini = abs(row[j])
			sum += abs(row[j])
	if countneg % 2 != 0:
		print(sum - 2 * mini)
	else:
		print(sum)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	matrix = []
	for _ in range(n):
		(*row,) = map(int, input().split())
		matrix.append(row)
	sign = 0
	s = 0
	mn = abs(matrix[0][0])
	for row in matrix:
		for v in row:
			if v < 0:
				sign = 1 - sign
			s += abs(v)
			mn = min(mn, abs(v))
	if sign == 0:
		print(s)
	else:
		print(s - 2 * mn)


import sys
for _ in range(int(sys.stdin.readline())):
	a = list(map(int, sys.stdin.readline().strip().split(' ')))
	s = 0
	m = 1000
	n = 0
	for i in range(a[0]):
		b = list(map(int, sys.stdin.readline().strip().split(' ')))
		for j in b:
			if j < 0:
				n += 1
		c = [abs(j) for j in b]
		s += sum(c)
		m = min(m, min(c))
	if n % 2 == 1:
		s -= 2 * m
	print(s)


for _ in range(0, int(input())):
	(n, m) = map(int, input().split())
	mat = [[int(x) for x in input().split()] for _ in range(0, n)]
	odd = 0
	mnm = 1 << 30
	ans = 0
	for i in range(0, n):
		abss = list(map(abs, mat[i]))
		ans += sum(abss)
		odd += len(list(filter(lambda x: x <= 0, mat[i])))
		if len(abss):
			mnm = min(mnm, min(abss))
	if odd & 1:
		ans -= 2 * mnm
	print(ans)


import sys
input = sys.stdin.readline

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

def instr():
	return str(input())

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

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

def invr():
	return map(int, input().split())
from collections import Counter

def main():
	t = inp()
	for _ in range(t):
		(n, m) = inlt()
		all_pos = True
		nums = []
		for i in range(n):
			in_nums = inlt()
			for num in in_nums:
				if num < 0:
					all_pos = not all_pos
				nums.append(abs(num))
		nums.sort()
		if not all_pos:
			nums[0] = -nums[0]
		print(sum(nums))
main()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	matrix = []
	for i in range(n):
		matrix.append(list(map(int, input().split())))
	count = 0
	sum = 0
	minimum = float('inf')
	for i in matrix:
		for ele in i:
			sum += abs(ele)
			minimum = min(minimum, abs(ele))
			if ele < 0:
				count += 1
	if count % 2 == 0:
		print(sum)
	else:
		print(sum - 2 * minimum)


def solve():
	(n, m) = map(int, input().split())
	c = 0
	l = []
	for i in range(n):
		l1 = list(map(int, input().split()))
		for j in l1:
			if j < 0:
				c += 1
			l.append(abs(j))
	if c % 2 == 0:
		return sum(l)
	elif l.count(0) > 0:
		return sum(l)
	else:
		return sum(l) - 2 * min(l)
for _ in range(int(input())):
	print(solve())


import sys
import time
import os
from math import sqrt, log, log2, log10, gcd, floor, pow, sin, cos, tan, pi, inf, factorial
from copy import copy, deepcopy
from sys import exit, stdin, stdout
from collections import Counter, defaultdict, deque
from itertools import permutations
import heapq
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
mod = 1000000007
iinp = lambda : int(sys.stdin.readline())
inp = lambda : sys.stdin.readline().strip()
strl = lambda : list(inp().strip().split(' '))
intl = lambda : list(map(int, inp().split(' ')))
mint = lambda : map(int, inp().split())
flol = lambda : list(map(float, inp().split(' ')))
flush = lambda : stdout.flush()

def permute(nums):

	def fun(arr, nums, cur, v):
		if len(cur) == len(nums):
			arr.append(cur.copy())
		i = 0
		while i < len(nums):
			if v[i]:
				i += 1
				continue
			else:
				cur.append(nums[i])
				v[i] = 1
				fun(arr, nums, cur, v)
				cur.pop()
				v[i] = 0
				i += 1
		return arr
	res = []
	nums.sort()
	v = [0] * len(nums)
	return fun(res, nums, [], v)

def subsets(res, index, arr, cur):
	res.append(cur.copy())
	for i in range(index, len(arr)):
		cur.append(arr[i])
		subsets(res, i + 1, arr, cur)
		cur.pop()
	return res

def sieve(N):
	root = int(sqrt(N))
	primes = [1] * (N + 1)
	(primes[0], primes[1]) = (0, 0)
	for i in range(2, root + 1):
		if primes[i]:
			for j in range(i * i, N + 1, i):
				primes[j] = 0
	return primes

def bs(arr, l, r, x):
	if x < arr[0] or x > arr[len(arr) - 1]:
		return -1
	while l <= r:
		mid = l + (r - l) // 2
		if arr[mid] == x:
			return mid
		elif arr[mid] < x:
			l = mid + 1
		else:
			r = mid - 1
	return -1

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	p = int(sqrt(n))
	for i in range(5, p + 1, 6):
		if n % i == 0 or n % (i + 2) == 0:
			return False
	return True

def solve():
	(n, m) = mint()
	arr = []
	s = 0
	neg = 0
	m = -1000000
	for i in range(n):
		a = intl()
		for j in a:
			s += abs(j)
			if j < 0:
				neg += 1
			m = min(abs(m), abs(j))
		arr.append(a)
	if neg % 2 == 0:
		print(s)
		return
	else:
		print(s - 2 * abs(m))
		return
start_time = time.time()
for _ in range(iinp()):
	solve()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline()

def RL():
	return map(int, sys.stdin.readline().split())

def RLL():
	return list(map(int, sys.stdin.readline().split()))

def N():
	return int(input())

def print_list(l):
	print(' '.join(map(str, l)))
import bisect as bs
for _ in range(N()):
	(n, m) = RL()
	d = []
	for _ in range(n):
		d += RLL()
	d.sort()
	t = bs.bisect_right(d, 0)
	res = sum(d[t:]) - sum(d[:t])
	if t & 1:
		if t < n * m:
			res -= 2 * min(-d[t - 1], d[t])
		else:
			res += 2 * d[-1]
	print(res)


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


from sys import stdout, stdin, setrecursionlimit
from io import BytesIO, IOBase
from collections import *
from itertools import *
from bisect import *
from string import *
from queue import *
from heapq import *
from math import *
from re import *
from os import *

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(stdin, stdout) = (IOWrapper(stdin), IOWrapper(stdout))
(graph, mod, szzz) = ({}, 10 ** 9 + 7, lambda : sorted(zzz()))

def getStr():
	return input()

def getInt():
	return int(input())

def listStr():
	return list(input())

def getStrs():
	return input().split()

def isInt(s):
	return '0' <= s[0] <= '9'

def input():
	return stdin.readline().strip()

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

def output(answer, end='\n'):
	stdout.write(str(answer) + end)

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)
dx = [-1, 1, 0, 0, 1, -1, 1, -1]
dy = [0, 0, 1, -1, 1, -1, -1, 1]
daysInMounth = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
num = getInt()
for _ in range(num):
	(n, m) = zzz()
	s = 0
	mn = float('inf')
	neg = 0
	for j in range(n):
		arr = zzz()
		for i in arr:
			s += abs(i)
			if i < 0:
				neg += 1
			mn = min(mn, abs(i))
	print(s - 2 * mn if neg % 2 else s)


import os
import sys
from io import BytesIO, IOBase

def main():
	for t in range(int(input())):
		(n, m) = map(int, input().split())
		nummins = 0
		abssum = 0
		minabs = 10000000
		for i in range(n):
			ms = list(map(int, input().split()))
			for m in ms:
				abssum += abs(m)
				if m < 0:
					nummins += 1
				if abs(m) < minabs:
					minabs = abs(m)
		if nummins % 2 == 0:
			print(abssum)
		else:
			print(abssum - 2 * minabs)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ans = 0
	cn = 0
	val = 1000000
	for p in range(n):
		B = list(map(int, input().split()))
		for i in range(len(B)):
			if B[i] < 0:
				cn += 1
			ans += abs(B[i])
			val = min(val, abs(B[i]))
	if cn % 2 != 0:
		ans -= 2 * val
	print(ans)


import sys
try:
	(sys.stdin, sys.stdout) = (open('in.txt', 'r'), open('out.txt', 'w'))
except:
	pass
ii1 = lambda : int(sys.stdin.readline().strip())
is1 = lambda : sys.stdin.readline().strip()
iia = lambda : list(map(int, sys.stdin.readline().strip().split()))
isa = lambda : sys.stdin.readline().strip().split()
mod = int(1000000000.0 + 7)
from collections import *
from math import *
from itertools import *
for _ in range(ii1()):
	(n, m) = iia()
	arr = []
	for i in range(n):
		arr.append(iia())
	sm = 0
	total = []
	count = 0
	for i in range(n):
		for j in range(m):
			if arr[i][j] < 0:
				count += 1
			sm += abs(arr[i][j])
			total.append(abs(arr[i][j]))
	if count % 2 == 0:
		print(sum(total))
	else:
		a = min(total)
		print(sm - 2 * a)


for t in range(int(input())):
	(n, m) = [int(k) for k in input().split()]
	neg = 0
	sm = 0
	num = []
	for i in range(n):
		row = [int(k) for k in input().split()]
		for ele in row:
			sm += abs(ele)
			if ele <= 0:
				neg += 1
			num += [abs(ele)]
	if neg % 2:
		num.sort()
		sm -= num[0]
		sm -= num[0]
	print(sm)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [list(map(int, input().split())) for i in range(n)]
	(neg, m, s) = (0, 100, 0)
	for each in a:
		for v in each:
			m = min(m, abs(v))
			if v < 0:
				neg += 1
			s += abs(v)
	if not neg or neg % 2 == 0:
		print(s)
	else:
		print(s - 2 * m)


t = int(input())
for p in range(t):
	(n, m) = map(int, input().split())
	a = [list(map(int, input().split())) for i in range(n)]
	neg = nil = s = 0
	minmod = abs(a[0][0])
	for i in range(n):
		for j in range(m):
			if abs(a[i][j]) < minmod:
				minmod = abs(a[i][j])
			if a[i][j] < 0:
				neg += 1
			elif a[i][j] == 0:
				nil += 1
			s += abs(a[i][j])
	if nil > 0 or neg % 2 == 0:
		print(s)
	else:
		print(s - 2 * minmod)


for i in range(int(input())):
	count = 0
	rs = 0
	sub = list(map(int, input().split()))
	minA = 999
	for j in range(sub[0]):
		a = input()
		count += a.count('-')
		arr = list(map(int, a.split()))
		arr = [abs(i) for i in arr]
		rs += sum(arr)
		minAr = min(arr)
		minA = min(minAr, minA)
	if count % 2 == 0:
		print(rs)
	else:
		print(rs - minA * 2)


import sys
input = sys.stdin.readlines()

def nb(arr):
	neg_count = 0
	mn = float('inf')
	s = 0
	for row in arr:
		for n in row:
			mn = min(abs(n), mn)
			if n <= 0:
				neg_count += 1
			s += abs(n)
	if neg_count % 2 == 0:
		return s
	else:
		return s - 2 * mn
for i in range(len(input)):
	input[i] = input[i].split()
	input[i] = [int(x) for x in input[i]]
num_test_cases = input[0][0]
k = 1
test_cases = []
while k < len(input):
	arr = []
	d = input[k][0]
	for i in range(k + 1, k + d + 1):
		arr.append(input[i])
	test_cases.append(arr.copy())
	k += d + 1
for case in test_cases:
	print(nb(case))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	d = list()
	s = 0
	ans = 0
	l = list()
	for i in range(n):
		a = list(map(int, input().split()))
		for k in a:
			if k < 0:
				ans += 1
			s += abs(k)
			l.append(abs(k))
	if ans % 2 == 1:
		s = s - 2 * min(l)
	print(s)


import os
import sys
from io import BytesIO, IOBase
import heapq as h
import bisect
from types import GeneratorType
BUFSIZE = 8192

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import collections as col
import math, string

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())
MOD = 10 ** 9 + 7
mod = 10 ** 9 + 7
t = int(input())
p = 10 ** 9 + 7

def ncr_util():
	inv[0] = inv[1] = 1
	fact[0] = fact[1] = 1
	for i in range(2, 300001):
		inv[i] = inv[i % p] * (p - p // i) % p
	for i in range(1, 300001):
		inv[i] = inv[i - 1] * inv[i] % p
		fact[i] = fact[i - 1] * i % p

def z_array(s1):
	n = len(s1)
	z = [0] * n
	(l, r, k) = (0, 0, 0)
	for i in range(1, n):
		if i > r:
			(l, r) = (i, i)
			while r < n and s1[r - l] == s1[r]:
				r += 1
			z[i] = r - l
			r -= 1
		else:
			k = i - l
			if z[k] < r - i + 1:
				z[i] = z[k]
			else:
				l = i
				while r < n and s1[r - l] == s1[r]:
					r += 1
				z[i] = r - l
				r -= 1
	return z

def solve():
	(suma, mini, cnt) = (0, 101, 0)
	for i in range(n):
		for j in range(m):
			if l[i][j] < 0:
				cnt += 1
			suma += abs(l[i][j])
			mini = min(mini, abs(l[i][j]))
	if cnt % 2 == 0:
		return suma
	return suma - 2 * mini
for _ in range(t):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		l.append(list(map(int, input().split())))
	print(solve())


def readInt():
	return int(input())

def readLine():
	return [int(s) for s in input().split(' ')]

def readString():
	return input()
t = readInt()

def ask(st):
	negs = 0
	min = 1000000007
	sum = 0
	for a in st:
		for b in a:
			if abs(b) < min:
				min = abs(b)
			sum += abs(b)
			if b <= 0:
				negs += 1
	if negs % 2 == 0:
		return sum
	else:
		return sum - 2 * min
for _ in range(t):
	(a, b) = readLine()
	ret = []
	for _ in range(a):
		ret.append(readLine())
	result = ask(ret)
	print(result)


import os
import sys
from io import BytesIO, IOBase
from collections import defaultdict
import math
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	s = 0
	m = 999999999999
	minus = 0
	zeroes = 0
	for i in range(n):
		l = list(map(int, input().split(' ')))
		for j in l:
			if j < 0:
				minus += 1
			if j == 0:
				zeroes += 1
			m = min(m, abs(j))
			s += abs(j)
	if minus == 0:
		print(s)
	elif minus % 2:
		if zeroes:
			print(s)
		else:
			print(s - 2 * m)
	else:
		print(s)


import math
t = int(input())
for y in range(t):
	maxm = math.inf
	(n, m) = list(map(int, input().split()))
	neg = 0
	sum = 0
	for h in range(n):
		d = list(map(int, input().split()))
		for u in d:
			if u < 0:
				neg += 1
			if abs(u) < maxm:
				maxm = abs(u)
			sum += abs(u)
	if neg % 2 != 0:
		sum -= 2 * maxm
	print(sum)


for _ in range(int(input())):
	l1 = []
	(n, m) = list(map(int, input().strip().split()))
	for i in range(n):
		l2 = list(map(int, input().strip().split()))
		l1.append(l2)
	g = 0
	sum1 = 0
	h = 101
	v = 0
	for i in range(n):
		for j in range(m):
			if l1[i][j] == 0:
				v = 1
			elif l1[i][j] < 0:
				e = -l1[i][j]
				g += 1
				sum1 += e
				if e < h:
					h = e
			else:
				e = l1[i][j]
				sum1 += e
				if e < h:
					h = e
	if g % 2 == 0 or v == 1:
		print(sum1)
	else:
		print(sum1 - 2 * h)


for _ in range(int(input())):
	(m, n) = map(int, input().split())
	s = a = b = 0
	ma = 2 ** 32
	for i in range(m):
		x = map(int, input().split())
		for j in x:
			if j < 0:
				a += 1
				s += abs(j)
			else:
				b += 1
				s += abs(j)
			ma = min(ma, abs(j), abs(j))
	if a % 2 != 0:
		s -= ma * 2
	print(s)


from functools import lru_cache
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = []
	mn = 1000000000.0
	neg_amount = 0
	s = 0
	for i in range(n):
		tmp = list(map(int, input().split()))
		s += sum([abs(x) for x in tmp])
		neg_amount += sum((1 for i in tmp if i < 0))
		for i in tmp:
			mn = min(mn, abs(i))
		arr.append(tmp)
	if neg_amount % 2 == 0:
		print(s)
	else:
		print(s - 2 * mn)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	mat = []
	minneg = -10 ** 9
	minpos = 10 ** 9
	summat = 0
	negnum = 0
	flag = False
	for i in range(n):
		row = list(map(int, input().split()))
		for j in row:
			if j < 0:
				negnum += 1
				if j > minneg:
					minneg = j
				summat += -1 * j
			elif j > 0:
				summat += j
				if j < minpos:
					minpos = j
			else:
				flag = True
	if flag:
		print(summat)
	elif negnum % 2:
		if abs(minpos) > abs(minneg):
			print(summat + 2 * minneg)
		else:
			print(summat - 2 * minpos)
	else:
		print(summat)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(n):
		arr.append(list(map(int, input().split())))
	minn = 10 ** 18
	summ = 0
	neg = 0
	for i in range(n):
		for j in range(m):
			minn = min(abs(arr[i][j]), minn)
			if arr[i][j] < 0:
				neg += 1
			summ += abs(arr[i][j])
	if neg % 2 == 0:
		print(summ)
	else:
		print(summ - 2 * minn)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	lowest_val = float('inf')
	sum = 0
	amount_of_neg = 0
	zero = False
	for j in range(n):
		inp = map(int, input().split())
		for val in inp:
			if abs(val) < lowest_val:
				lowest_val = abs(val)
			if val == 0:
				zero = True
			if val < 0:
				amount_of_neg += 1
			sum += abs(val)
	if not zero and amount_of_neg % 2 == 1:
		sum -= 2 * lowest_val
	print(sum)


for _ in range(int(input())):
	(r, c) = map(int, input().split())
	l = []
	p = []
	for i in range(r):
		t = list(map(int, input().split()))
		l.extend(t)
	c = 0
	for i in l:
		if i < 0:
			p.append(i * -1)
			c += 1
		else:
			p.append(i)
	su = sum(p)
	if c % 2 == 0:
		print(su)
	else:
		print(su - 2 * min(p))


def main():
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		mm = []
		cnt = 0
		mn = 1000
		sm = 0
		flag = 0
		for i in range(n):
			l = list(map(int, input().split()))
			mm.append(l)
			for j in l:
				sm += abs(j)
				if j == 0:
					flag = 1
				if j < 0:
					cnt += 1
				mn = min(mn, abs(j))
		if flag:
			ans = sm
		elif cnt & 1:
			ans = sm - 2 * mn
		else:
			ans = sm
		print(ans)
main()


def Signum(x):
	return -1 if x < 0 else 0 if x == 0 else 1
for _ in range(int(input())):
	(n, m) = input().split()
	(Total, Zeros, Negatives, Minabs) = (0, 0, 0, 1000)
	for _ in range(int(n)):
		Row = list(map(int, input().split()))
		for i in Row:
			if Signum(i) == -1:
				Negatives += 1
			if Signum(i) == 0:
				Zeros += 1
			iAbs = abs(i)
			if Minabs > iAbs:
				Minabs = iAbs
			Total += iAbs
	if Zeros > 0 or Negatives % 2 == 0:
		print(Total)
	else:
		print(Total - 2 * Minabs)


for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	(ans, mn) = (0, 100)
	count = 0
	for i in range(n):
		temp = list(map(int, input().split()))
		for elt in temp:
			ans += abs(elt)
			mn = min(mn, abs(elt))
			if elt < 0:
				count += 1
	if count % 2 == 0:
		print(ans)
	else:
		print(ans - 2 * mn)


def check(a, r, c):
	summ = 0
	minn = 99999999
	evn = 0
	for i in a:
		for j in i:
			if j <= 0:
				evn += 1
			summ += abs(j)
			minn = min(minn, abs(j))
	if evn % 2 == 0:
		return summ
	return summ - 2 * minn
for _ in range(int(input())):
	(r, c) = map(int, input().split())
	a = []
	for i in range(r):
		a.append(list(map(int, input().split())))
	print(check(a, r, c))


t = int(input())
for i in range(0, t):
	k = []
	(n, m) = list(map(int, input().split(' ')))
	for i in range(0, n):
		k.append(list(map(int, input().split(' '))))
	flag = 0
	for i in range(0, len(k)):
		if 0 in k[i]:
			flag = 1
			break
	s = 0
	p = 10000000
	q = 0
	for i in range(0, len(k)):
		for j in range(0, len(k[i])):
			if k[i][j] < 0:
				q += 1
			s += abs(k[i][j])
			p = min(p, abs(k[i][j]))
	if flag == 1:
		print(s)
	elif q % 2 == 0:
		print(s)
	else:
		print(s - 2 * p)


import sys
import math
from sys import stdin, stdout

def sieve(N):
	primeNumbers = [True] * (N + 1)
	primeNumbers[0] = False
	primeNumbers[1] = False
	i = 2
	while i * i <= N:
		j = i
		if primeNumbers[j]:
			while j * i <= N:
				primeNumbers[j * i] = False
				j += 1
		i += 1
	return primeNumbers

def getPrime(N):
	primes = sieve(N)
	result = []
	for i in range(len(primes)):
		if primes[i]:
			result.append(i)
	return result

def factor(N):
	factors = []
	i = 1
	while i * i <= N:
		if N % i == 0:
			factors.append(i)
			if i != N // i:
				factors.append(N // i)
		i += 1
	return sorted(factors)

def gcd(a, b):
	if a < b:
		return gcd(b, a)
	if b == 0:
		return a
	return gcd(b, a % b)

def extendedGcd(a, b):
	if a < b:
		return extendedGcd(b, a)
	if b == 0:
		return [a, 1, 0]
	res = extendedGcd(b, a % b)
	x = res[2]
	y = res[1] - math.floor(a / b) * res[2]
	res[1] = x
	res[2] = y
	return res

def iterativeModularFunc(a, b, c):
	res = 1
	while b > 0:
		if b & 1:
			res = res * a % c
		a = a * a % c
		b = b // 2
	return res

def get_ints_in_variables():
	return map(int, sys.stdin.readline().strip().split())

def get_int():
	return int(input())

def get_ints_in_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_list_of_list(n):
	return [list(map(int, sys.stdin.readline().strip().split())) for _ in range(n)]

def get_string():
	return sys.stdin.readline().strip()

def addV(matrix, n, m, i, j):
	pass

def Solution(matrix, n, m):
	ans = 0
	minusCount = 0
	sm = float('inf')
	for i in range(n):
		for j in range(m):
			if matrix[i][j] <= 0:
				minusCount += 1
			if sm > abs(matrix[i][j]):
				sm = abs(matrix[i][j])
			ans += abs(matrix[i][j])
	if minusCount % 2 == 1:
		print(ans - 2 * sm)
	else:
		print(ans)

def main():
	for _ in range(get_int()):
		(n, m) = get_ints_in_variables()
		matrix = get_list_of_list(n)
		Solution(matrix, n, m)
main()


import collections

def f():
	n = int(input())
	for i in range(n):
		dim = [int(x) for x in input().strip().split()]
		min = 101
		nc = 0
		sum = 0
		for _ in range(dim[0]):
			arr = [int(x) for x in input().strip().split()]
			for x in arr:
				sum += abs(x)
				if x < 0:
					nc += 1
				if abs(x) < min:
					min = abs(x)
		if nc % 2 == 0:
			print(sum)
		else:
			print(sum - 2 * min)
f()


from sys import stdin
input = stdin.readline
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = [0] * (n * m)
	negs = 0
	for i in range(n):
		k = list(map(int, input().split()))
		for j in range(m):
			a[m * i + j] = abs(k[j])
			if k[j] < 0:
				negs += 1
	a.sort()
	negs %= 2
	s = sum(a) - 2 * sum(a[:negs])
	print(s)


for _ in range(int(input())):
	(n, m) = [int(j) for j in input().split()]
	b = []
	for i in range(n):
		a = [int(j) for j in input().split()]
		b = b + a
	c = 0
	for k in b:
		if k <= 0:
			c = c + 1
	if c % 2 != 0:
		d = []
		for t in b:
			d.append(abs(t))
		print(sum(d) - 2 * min(d))
	else:
		d = []
		for t in b:
			d.append(abs(t))
		print(sum(d))


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


t = int(input())
j = 0
while j < t:
	a = input().split(' ')
	n = int(a[0])
	m = int(a[1])
	i = 0
	b = []
	while i < n:
		x = input().split(' ')
		for num in x:
			b.append(int(num))
		i += 1
	neg_count = 0
	small = abs(b[0])
	X = 0
	for z in b:
		if z <= 0:
			neg_count += 1
			z = z * -1
		if abs(z) < small:
			small = z
		X += z
	if neg_count % 2 != 0:
		X = X - 2 * small
	print(X)
	j += 1


for i in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	for j in range(n):
		b = list(map(int, input().split()))
		a.append(b)
	cnt = 0
	sum = 0
	mina = 10 ** 18
	for j in range(n):
		for k in range(m):
			if a[j][k] < 0:
				cnt += 1
			sum += abs(a[j][k])
			mina = min(mina, abs(a[j][k]))
	if cnt % 2 == 0:
		print(sum)
	else:
		print(sum - 2 * mina)


t = int(input())
for i in range(t):
	a = list(map(int, input().split()))
	m = a[0]
	n = a[1]
	mat = []
	for i in range(m):
		mat.append(list(map(int, input().split())))
	negcount = 0
	minmat = 2000000000
	total = 0
	for i in range(m):
		for j in range(n):
			total += abs(mat[i][j])
			minmat = min(minmat, abs(mat[i][j]))
			if mat[i][j] < 0:
				negcount += 1
	if negcount & 1:
		print(total - 2 * minmat)
	else:
		print(total)


def solve():
	pass
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	(cnt_negative, min_value, sm) = (0, 100, 0)
	for i in range(n):
		for x in map(int, input().split()):
			min_value = min(min_value, abs(x))
			sm += abs(x)
			if x < 0:
				cnt_negative += 1
	if cnt_negative % 2 == 0:
		print(sm)
	else:
		print(sm - 2 * min_value)


def sol(arr):
	min = 101
	count = 0
	sum = 0
	for i in range(len(arr)):
		for j in range(len(arr[0])):
			if arr[i][j] <= 0:
				arr[i][j] = abs(arr[i][j])
				count = count + 1
			if arr[i][j] < min:
				min = arr[i][j]
			sum = sum + arr[i][j]
	if count % 2 != 0:
		sum = sum - 2 * min
	return sum
for i in range(int(input())):
	m = list(map(int, input().split()))
	arr = [[0] * m[1]] * m[0]
	for i in range(m[0]):
		arr[i] = list(map(int, input().split()[:m[1]]))
	print(sol(arr))


for _ in range(int(input())):
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	lis = [0] * n * m
	for i in range(n):
		lisa = list(map(int, input().split()))
		lis[i * m:(i + 1) * m] = lisa
	x = 0
	y = max(lis)
	for i in range(len(lis)):
		if lis[i] < 0:
			x += 1
			lis[i] = abs(lis[i])
		if lis[i] != 0 and lis[i] < y:
			y = lis[i]
	if x % 2 == 0:
		print(sum(lis))
	elif x % 2 != 0 and min(lis) == 0:
		print(sum(lis))
	else:
		print(sum(lis) - 2 * abs(y))


import sys
t = int(input())
for num in range(t):
	(n, m) = map(int, sys.stdin.readline().split())
	grid = []
	for row in range(n):
		column = list(map(int, sys.stdin.readline().split()))
		grid.append(column)
	count = 0
	total = 0
	least = 101
	for i in range(n):
		for j in range(m):
			if grid[i][j] < 0:
				count += 1
				total += grid[i][j] * -1
				if grid[i][j] * -1 < least:
					least = grid[i][j] * -1
			else:
				total += grid[i][j]
				if grid[i][j] < least:
					least = grid[i][j]
	if count % 2 == 1:
		total -= least * 2
	print(total)


import sys
max_int = 1000000001
min_int = -max_int
t = int(input())
for _t in range(t):
	min_abs = max_int
	sum_abs = 0
	neg_count = 0
	(rows, cols) = map(int, sys.stdin.readline().split())
	for i in range(rows):
		row = map(int, sys.stdin.readline().split())
		for one in row:
			if one <= 0:
				neg_count += 1
			min_abs = min(min_abs, abs(one))
			sum_abs += abs(one)
	if neg_count % 2:
		print(sum_abs - 2 * min_abs)
	else:
		print(sum_abs)


a = int(input())
for i in range(a):
	(n, m) = map(int, input().split())
	arr = []
	minn = float('inf')
	for i in range(n):
		temp = list(map(int, input().split()))
		arr.append(temp)
	count = 0
	for i in range(n):
		for j in range(m):
			if arr[i][j] < 0:
				count = count + 1
	summ = 0
	for i in range(n):
		for j in range(m):
			summ = summ + abs(arr[i][j])
			minn = min(minn, abs(arr[i][j]))
	if count % 2 == 0:
		print(summ)
	else:
		print(summ - 2 * abs(minn))


t = int(input())

def solve(l):
	n = len(l)
	m = len(l[0])
	for i in range(n):
		for j in range(m):
			if l[i][j] < 0:
				if i - 1 >= 0 and l[i - 1][j] <= 0:
					l[i][j] *= -1
					l[i - 1][j] *= -1
				elif j - 1 >= 0 and l[i][j - 1] <= 0:
					l[i][j] *= -1
					l[i][j - 1] *= -1
				elif j + 1 < m and l[i][j + 1] <= 0:
					l[i][j] *= -1
					l[i][j + 1] *= -1
				elif i + 1 < n and l[i + 1][j] <= 0:
					l[i][j] *= -1
					l[i + 1][j] *= -1
				else:
					z = 10 ** 18
					if i - 1 >= 0:
						z = min(z, l[i - 1][j])
					if j - 1 >= 0:
						z = min(z, l[i][j - 1])
					if i + 1 < n:
						z = min(z, l[i + 1][j])
					if j + 1 < m:
						z = min(z, l[i][j + 1])
					if z < abs(l[i][j]):
						if i - 1 >= 0 and z == l[i - 1][j]:
							l[i][j] *= -1
							l[i - 1][j] *= -1
						elif j - 1 >= 0 and z == l[i][j - 1]:
							l[i][j] *= -1
							l[i][j - 1] *= -1
						elif i + 1 < n and z == l[i + 1][j]:
							l[i][j] *= -1
							l[i + 1][j] *= -1
						elif j + 1 < m and z == l[i][j + 1]:
							l[i][j] *= -1
							l[i][j + 1] *= -1
	return l
for _ in range(t):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		la = list(map(int, input().split()))
		l.append(la)
	cnt = 0
	ans = 0
	flag = 0
	mini = 10 ** 18
	for i in range(n):
		for j in range(m):
			ans += abs(l[i][j])
			if l[i][j] < 0:
				cnt += 1
			if l[i][j] == 0:
				flag = 1
			mini = min(abs(l[i][j]), mini)
	if flag or cnt % 2 == 0:
		print(ans)
	else:
		ans -= 2 * mini
		print(ans)


import math

def run():
	t = int(input())
	for _ in range(t):
		(n, m) = tuple(map(int, input().split()))
		zeros = 0
		negs = 0
		abs_min = math.inf
		s = 0
		for _ in range(n):
			row = tuple(map(int, input().split()))
			for i in row:
				if i == 0:
					zeros += 1
				if i < 0:
					negs += 1
				s += abs(i)
				if i != 0 and abs(i) < abs_min:
					abs_min = abs(i)
		if zeros == 0 and negs % 2 != 0:
			print(s - abs_min * 2)
		else:
			print(s)
run()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(negative, minn) = (0, 100)
	ans = 0
	for i in range(n):
		k = list(map(int, input().split()))
		for j in k:
			if j < 0:
				negative += 1
			minn = min(minn, abs(j))
			ans += abs(j)
	if negative % 2 == 0:
		print(ans)
	else:
		print(ans - 2 * minn)


for _ in range(int(input())):
	(row, col) = map(int, input().split())
	arr = []
	for i in range(row):
		l = list(map(int, input().split()))
		arr.extend(l)
	neg = 0
	for i in arr:
		if i < 0:
			neg += 1
	for i in range(len(arr)):
		arr[i] = abs(arr[i])
	s = sum(arr)
	mini = min(arr)
	if neg % 2 == 0:
		print(s)
	else:
		print(s - 2 * mini)


num_inp = lambda : int(input())
arr_inp = lambda : list(map(int, input().split()))
sp_inp = lambda : map(int, input().split())
str_inp = lambda : input()
for i in range(int(input())):
	(n, m) = map(int, input().split())
	(l, k) = ([], 0)
	for i in range(n):
		l += [*map(int, input().split())]
	for i in range(n * m):
		if l[i] < 0:
			k += 1
			l[i] *= -1
	print(sum(l) - k % 2 * min(l) * 2)


inn = lambda : int(input())
inm = lambda : map(int, input().split())
ins = lambda : str(input())
ina = lambda : list(map(int, input().split()))

def solve():
	(n, m) = inm()
	b = []
	for i in range(n):
		b += ina()
	x = 0
	if 0 in b:
		for i in b:
			x += abs(i)
		print(x)
	else:
		lz = 0
		for i in b:
			lz += i < 0
		if lz % 2 == 0:
			for i in b:
				x += abs(i)
			print(x)
		else:
			c = []
			d = []
			for i in b:
				x += abs(i)
				if i < 0:
					c.append(i)
				else:
					d.append(i)
			x = x + 2 * max(c)
			y = x
			if len(d):
				y = x - 2 * (max(c) + min(d))
			print(max(x, y))

def main():
	t = 1
	t = int(input())
	for _ in range(t):
		solve()
main()


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
import time
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())

def getMat(n):
	return [getInts() for _ in range(n)]
MOD = 10 ** 9 + 7

def solve():
	(N, M) = getInts()
	grid = getMat(N)
	min_el = 10 ** 18
	count_neg = 0
	count_zero = 0
	sum_el = 0
	for i in range(N):
		for j in range(M):
			if grid[i][j] < 0:
				count_neg += 1
			elif grid[i][j] == 0:
				count_zero += 1
			min_el = min(min_el, abs(grid[i][j]))
			sum_el += abs(grid[i][j])
	if count_neg % 2 == 0 or count_zero > 0:
		return sum_el
	return sum_el - 2 * min_el
for _ in range(getInt()):
	print(solve())


import os
import sys
from math import *
from collections import *
from bisect import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ALPHA = 'abcdefghijklmnopqrstuvwxyz/'
M = 1000000007
EPS = 1e-06

def Ceil(a, b):
	return a // b + int(a % b > 0)

def value():
	return tuple(map(int, input().split()))

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

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
for _ in range(Int()):
	(n, m) = value()
	a = []
	for i in range(n):
		a.append(array())
	neg = 0
	s = 0
	mi = inf
	for i in range(n):
		for j in range(m):
			if a[i][j] < 0:
				neg += 1
			s += abs(a[i][j])
			mi = min(abs(a[i][j]), mi)
	if neg % 2:
		s -= 2 * mi
	print(s)


import sys
from sys import stdin
tt = int(stdin.readline())
for _ in range(tt):
	(n, m) = map(int, stdin.readline().split())
	matrix = [list(map(int, stdin.readline().split())) for l in range(n)]
	neg = 0
	for i in range(n):
		for j in range(m):
			if matrix[i][j] <= 0:
				neg += 1
	if neg % 2 == 0:
		print(sum([sum(map(abs, x)) for x in matrix]))
	else:
		min_abs = min([min(map(abs, x)) for x in matrix])
		print(sum([sum(map(abs, x)) for x in matrix]) - min_abs * 2)


t = int(input())
for _ in range(t):
	(n, m) = [int(x) for x in input().split()]
	a = [[int(x) for x in input().split()] for i in range(n)]
	b = 0
	sum_ = 0
	min_ = 101
	for row in range(n):
		for column in range(m):
			y = a[row][column]
			sum_ += abs(y)
			if abs(y) < min_:
				min_ = abs(y)
			if y <= 0:
				b += 1
	if b % 2 == 0:
		print(sum_)
	else:
		print(sum_ - 2 * min_)


import os
import sys
from io import BytesIO, IOBase
_str = str
BUFSIZE = 8192

def str(x=b''):
	return x if type(x) is bytes else _str(x).encode()

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

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

def mpint():
	return map(int, inp().split(' '))

def itg():
	return int(inp())

def solve():
	(n, m) = mpint()
	data = []
	for _ in range(n):
		data.extend(mpint())
	s = sum(map(abs, data))
	if 0 in data:
		return s
	neg = sum(map(lambda a: 1 if a < 0 else 0, data))
	if neg & 1:
		return s - 2 * abs(min(data, key=abs))
	return s

def main():
	for _ in range(itg()):
		print(solve())
DEBUG = 0
URL = ''
if DEBUG == 1:
	import requests
	from ACgenerator.Y_Test_Case_Runner import TestCaseRunner
	runner = TestCaseRunner(main, URL)
	inp = runner.input_stream
	print = runner.output_stream
	runner.checking()
elif DEBUG == 2:
	main()
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
	main()


import sys

def answer(n, m, a):
	summ = 0
	best_mn = 101
	count_odds = 0
	for i in range(n):
		for j in range(m):
			summ += abs(a[i][j])
			best_mn = min(best_mn, abs(a[i][j]))
			if a[i][j] < 0:
				count_odds += 1
	if count_odds % 2 == 0:
		return summ
	else:
		return summ - 2 * best_mn

def main():
	t = int(input())
	while t:
		(n, m) = [int(i) for i in sys.stdin.readline().split()]
		a = []
		for j in range(n):
			a.append([int(i) for i in sys.stdin.readline().split()])
		print(answer(n, m, a))
		t -= 1
	return
main()


from sys import stdin
t = int(stdin.readline())
for _ in range(t):
	(n, k) = map(int, stdin.readline().split())
	ans = 0
	c = 0
	m = 100
	for i in range(n):
		for j in map(int, stdin.readline().split()):
			c += j < 0
			j = abs(j)
			ans += j
			m = min(m, j)
	if c % 2:
		print(ans - m * 2)
	else:
		print(ans)


t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	row = []
	matrix = [list(map(int, input().split())) for _ in range(n)]
	minimo = 101
	sum = 0
	neg = 0
	zero = False
	for i in range(n):
		for j in range(m):
			minimo = min(minimo, abs(matrix[i][j]))
			sum += abs(matrix[i][j])
			if matrix[i][j] < 0:
				neg += 1
			if matrix[i][j] == 0:
				zero = True
	if zero:
		print(sum)
	elif neg % 2 == 0:
		print(sum)
	else:
		ret = sum - 2 * minimo
		print(ret)


tests = int(input())
for test in range(tests):
	minimum = 100
	negatives = 0
	sum = 0
	istherezero = False
	table = input().split(' ')
	rows = int(table[0])
	coloums = int(table[1])
	for row in range(rows):
		onerow = input().split(' ')
		for coloum in range(coloums):
			if int(onerow[coloum]) == 0:
				istherezero = True
				minimum = 0
			elif int(onerow[coloum]) < 0:
				negatives += 1
				sum += abs(int(onerow[coloum]))
				if abs(int(onerow[coloum])) < minimum:
					minimum = abs(int(onerow[coloum]))
			else:
				sum += int(onerow[coloum])
				if int(onerow[coloum]) < minimum:
					minimum = int(onerow[coloum])
	if istherezero:
		print(sum)
	elif negatives % 2 == 0:
		print(sum)
	else:
		sum -= 2 * minimum
		print(sum)


t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	a = []
	for i in range(n):
		a.append(list(map(int, input().split())))
	(ans, m1, c, z) = (0, 101, 0, 0)
	for i in range(n):
		for j in range(m):
			ans = ans + abs(a[i][j])
			if a[i][j] == 0:
				z = 1
			if a[i][j] < 0:
				c = c + 1
			if abs(a[i][j]) < m1:
				m1 = abs(a[i][j])
	if c % 2 == 1:
		if z == 0:
			ans = ans - 2 * abs(m1)
	print(ans)


import io, os
from math import *
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [list(map(int, input().split())) for _ in range(n)]
	b = sorted([x for y in a for x in y])
	neg = [x for x in b if x < 0]
	pos = [x for x in b if x >= 0]
	if len(neg) % 2 == 0:
		print(sum(pos) - sum(neg))
	else:
		drop = -neg[-1]
		if pos:
			drop = min(drop, pos[0])
		print(sum(pos) - sum(neg) - 2 * drop)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(ans, f) = (0, 0)
	(mn, l) = (float('inf'), 0)
	for i in range(n):
		num = [*map(int, input().split())]
		for j in num:
			ans += abs(j)
			l += j < 0
			mn = min(mn, abs(j))
			if j == 0:
				f = 1
	print(ans - 2 * mn if not f and l % 2 else ans)


import bisect
import collections
import copy
import functools
import heapq
import itertools
import math
import random
import re
import sys
import time
import string
from typing import List
sys.setrecursionlimit(99999)
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	arr = []
	s = 0
	for _ in range(n):
		arr.append(list(map(int, input().split())))
	t = []
	x = 0
	for i in range(n):
		for j in range(m):
			s += abs(arr[i][j])
			t.append(abs(arr[i][j]))
			if arr[i][j] <= 0:
				x ^= 1
	if not x:
		print(s)
	else:
		t.sort()
		print(s - 2 * t[0])


import sys
import bisect as bi
import math
from collections import defaultdict as dd
import queue
import itertools
input = sys.stdin.readline
mo = 10 ** 9 + 7

def cin():
	return map(int, sin().split())

def ain():
	return list(map(int, sin().split()))

def sin():
	return input().strip()

def inin():
	return int(input())

def pref(a, n, f):
	pre = [0] * n
	if f == 0:
		pre[0] = a[0]
		for i in range(1, n):
			pre[i] = a[i] + pre[i - 1]
	else:
		pre[-1] = a[-1]
		for i in range(n - 2, -1, -1):
			pre[i] = pre[i + 1] + a[i]
	return pre
for _ in range(inin()):
	(n, m) = cin()
	mat = []
	for i in range(n):
		l = ain()
		mat += [l]
	s = 0
	mi = 111111111111135
	c = 0
	f = 0
	for i in range(n):
		for j in range(m):
			a = mat[i][j]
			if a == 0:
				f = 1
			if mat[i][j] < 0:
				c += 1
				a = abs(a)
			s += a
			mi = min(mi, a)
	if c % 2 and f == 0:
		print(s - mi - mi)
	else:
		print(s)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	total_neg = 0
	min_el = 100
	summ = 0
	for _ in range(n):
		arr = list(map(int, input().split()))
		for i in arr:
			if i < 0:
				total_neg += 1
			if abs(i) < min_el:
				min_el = abs(i)
			summ += abs(i)
	if total_neg % 2 == 0:
		print(summ)
	else:
		print(summ - 2 * min_el)


def solve():
	(n, m) = [int(v) for v in input().split()]
	numzero = 0
	numneg = 0
	smabs = 0
	minabs = 1000000000
	for _ in range(n):
		row = [int(v) for v in input().split()]
		for j in range(m):
			smabs += abs(row[j])
			minabs = min(abs(row[j]), minabs)
			if row[j] < 0:
				numneg += 1
			elif row[j] == 0:
				numzero += 1
	if numzero or numneg % 2 == 0:
		print(smabs)
	else:
		smabs -= 2 * minabs
		print(smabs)
t = int(input())
for _ in range(t):
	solve()


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	grid = [[int(i) for i in input().split()] for j in range(n)]
	(mina, suma, neg) = (101, 0, 0)
	for i in range(n):
		for j in range(m):
			mina = min(mina, abs(grid[i][j]))
			suma += abs(grid[i][j])
			if grid[i][j] < 0:
				neg += 1
	if neg % 2 == 1:
		ans = suma - 2 * mina
	else:
		ans = suma
	print(ans)


for _ in range(int(input())):
	(r, c) = map(int, input().split())
	a = []
	for i in range(r):
		x = list(map(int, input().split()))
		for j in x:
			a.append(j)
	count = 0
	for q in range(r * c):
		if a[q] < 0:
			count += 1
			a[q] = -a[q]
	if count % 2 == 0:
		print(sum(a))
	else:
		print(sum(a) - 2 * min(a))


t = int(input())
ansl = []
for i in range(t):
	(n, m) = map(int, input().split())
	totl = []
	for i in range(n):
		templ = list(map(int, input().split()))
		for i in templ:
			totl.append(i)
	suml = 0
	negatives = 0
	for i in range(len(totl)):
		if totl[i] < 0:
			negatives += 1
		totl[i] = abs(totl[i])
	if negatives % 2 == 0:
		suml = sum(totl)
	else:
		suml = sum(totl) - 2 * min(totl)
	ansl.append(suml)
for i in ansl:
	print(i)


t = int(input())
for test in range(t):
	(n, m) = [int(e) for e in input().split()]
	a = []
	for i in range(n):
		a.append([int(e) for e in input().split()])
	z = 0
	b = []
	for i in range(n):
		for j in range(m):
			if a[i][j] <= 0:
				z += 1
	for i in range(n):
		for j in range(m):
			b.append(abs(a[i][j]))
	b.sort()
	ans = 0
	if z % 2 == 0:
		for i in range(n):
			for j in range(m):
				ans += abs(a[i][j])
		f = True
	else:
		for i in range(n):
			for j in range(m):
				ans += abs(a[i][j])
		f = False
	if not f:
		ans -= 2 * b[0]
	print(ans)


t = int(input())
while t:
	t -= 1
	l = []
	(n, m) = map(int, input().split())
	for i in range(n):
		l.append([int(x) for x in input().split()])
	mi = 10 ** 9
	count = 0
	flag = True
	for i in range(n):
		for j in range(m):
			if flag and l[i][j] < 0:
				count += 1
			elif l[i][j] == 0:
				flag = False
				count = 0
			if abs(l[i][j]) < mi and abs(l[i][j]) > 0:
				a = i
				b = j
				mi = abs(l[i][j])
	sum = 0
	if count % 2:
		for i in range(n):
			for j in range(m):
				if i == a and j == b:
					if l[i][j] > 0:
						sum += -1 * l[i][j]
					else:
						sum += l[i][j]
				else:
					sum += abs(l[i][j])
	else:
		for i in range(n):
			for j in range(m):
				sum += abs(l[i][j])
	print(sum)


t = int(input())
for _ in range(t):
	(numNegs, numZeros) = (0, 0)
	(R, C) = map(int, input().split())
	grid = []
	result = 0
	elems = []
	for r in range(R):
		row = list(map(int, input().split()))
		C = len(row)
		for elem in row:
			elems.append(abs(elem))
			result += abs(elem)
			if elem < 0:
				numNegs += 1
			if elem == 0:
				numZeros += 1
	while numNegs >= 2:
		numNegs -= 2
	if numNegs == 0:
		print(result)
	else:
		print(result - 2 * min(elems))


from sys import stdin, stdout
from collections import Counter
from math import ceil
from bisect import bisect_left
from bisect import bisect_right

def ai():
	return list(map(int, stdin.readline().split()))

def ei():
	return map(int, stdin.readline().split())

def ip():
	return int(stdin.readline().strip())

def op(ans):
	return stdout.write(str(ans) + '\n')
for _ in range(ip()):
	(n, m) = ei()
	mat = []
	for i in range(n):
		mat.append(ai())
	neg = []
	pos = []
	for i in range(n):
		for j in range(m):
			if mat[i][j] <= 0:
				neg.append(mat[i][j])
			if mat[i][j] > 0:
				pos.append(mat[i][j])
	pos = sorted(pos)
	neg = sorted(neg)
	ans = 0
	i = 0
	while i < len(neg):
		try:
			ans += -1 * (neg[i] + neg[i + 1])
		except:
			break
		i += 2
	if len(neg) % 2 != 0:
		try:
			if pos[0]:
				if pos[0] < abs(neg[-1]):
					ans += abs(neg[-1])
					pos[0] *= -1
				else:
					ans += neg[-1]
		except:
			try:
				ans += neg[-1]
			except:
				pass
	ans += sum(pos)
	print(ans)


t = int(input())
for _ in range(t):
	(m, n) = map(int, input().split())
	nums = []
	pos = neg = zeros = 0
	for __ in range(m):
		line = list(map(int, input().split()))
		for i in range(n):
			nums.append(line[i])
			if line[i] > 0:
				pos += 1
			if line[i] < 0:
				neg += 1
			if line[i] == 0:
				zeros += 1
	res = 0
	if zeros != 0 or neg % 2 == 0:
		for num in nums:
			res += abs(num)
		print(res)
	else:
		abss = sorted([abs(num) for num in nums], reverse=True)
		print(sum(abss[:-1]) - abss[-1])


from math import *
a = int(input())
for i in range(a):
	minus = 0
	minmod1 = 0
	minmod2 = 1000
	mod = 0
	(n, m) = map(int, input().split())
	for j in range(n):
		line = [int(e) for e in input().split()]
		for h in line:
			if h < 0:
				minus += 1
		mod += sum([abs(g) for g in line])
		minmod1 = min([abs(g) for g in line])
		minmod2 = min(minmod1, minmod2)
	if minus % 2 == 1:
		print(mod - 2 * minmod2)
	else:
		print(mod)


import sys

def ints():
	return list(map(int, sys.stdin.readline().strip().split()))
tc = int(input())
while tc:
	tc -= 1
	(n, m) = map(int, input().split())
	(total, small) = (0, 99999999999)
	neg = 0
	mat = []
	for i in range(n):
		mat.append(ints())
		for j in range(m):
			if mat[-1][j] < 0:
				neg += 1
			total += abs(mat[-1][j])
			if small > abs(mat[-1][j]):
				small = abs(mat[-1][j])
	if neg % 2 == 0:
		small = 0
	print(total - 2 * small)


import random
t = int(input())
while t > 0:
	(ni, m) = map(int, input().split())
	l = []
	for i in range(ni):
		l.append(list(map(int, input().split())))
	ls = []
	a = 0
	n = 0
	z = 0
	p = 0
	for i in range(ni):
		for j in range(m):
			if l[i][j] > 0:
				p += 1
				ls.append(l[i][j])
			if l[i][j] < 0:
				n += 1
				ls.append(abs(l[i][j]))
			if l[i][j] == 0:
				z += 1
	if n % 2 == 0:
		print(sum(ls))
	elif z > 0:
		print(sum(ls))
	else:
		ls.sort()
		print(sum(ls[1:]) - ls[0])
	t -= 1


n = int(input(''))
for i in range(n):
	(m, n) = [int(_) for _ in input('').split()]
	arr = []
	for j in range(m):
		arr += [int(_) for _ in input('').split()]
	absarr = list(map(abs, arr))
	mini = min(absarr)
	prod = 1
	for i in arr:
		prod *= i
	if prod >= 0:
		print(sum(absarr))
	else:
		print(sum(absarr) - 2 * mini)


t = int(input())
for q in range(t):
	(x, y) = map(int, input().split())
	ans = 2 ** 32
	odd = val = 0
	for i in range(x):
		l = list(map(int, input().split()))
		for j in l:
			if j < 0:
				odd += 1
			val += abs(j)
			ans = min(ans, abs(j))
	if odd % 2 != 0:
		val -= ans * 2
	print(val)