This time Panda is doing great. He is good with mathematical problems. His teacher decided to puzzle him with summation problems.  

Consider the following definitions, assuming 1-based indexing:  

In the computation of B, one can choose +1 or -1 to multiply, for each arr[i].
Also, you are allowed to re-order the elements of arr, beforehand.

Help him find the maximum possible value of C.

Input Format
The first line contains T, the number of test cases.
Then N numbers follow.  

Output Format
Output the query of Panda in single line. Since the answer can be very large, mod it with 1000000007.  

Constraints

1 ≤ T ≤ 10
1 ≤ N ≤ 10^5
-10^9 ≤ arr[i] ≤ 10^9

Instructions
Write modular code  
Comment your code properly  

SAMPLE INPUT
1
4
1 2 3 4

SAMPLE OUTPUT
40
'''
for _ in range(input()):
	n = input()
	l = sorted(map(int,raw_input().split()),reverse=True)
	p,q = [],[]
	size_p = size_q = len(l)/2
	if len(l)%2==1: size_p += 1
	for i in range(size_p):
		p.append(l[i])
	for i in range(size_p,size_p+size_q):
		q.append(l[i])
	#print p,q
	#print l
	for i in range(len(l[:])):
		if l[i]<0: l[i] = (-1)*l[i]
	#print l
	answer = (sum(p)-sum(q))*(sum(l))
	#print p,sum(p)
	print answer
'''
for _ in range(input()):
        n = input()
        lst = map(int,raw_input().split())
        l = sorted(map(abs,lst),reverse=True)
        lst = sorted(lst,reverse=True)
        p,q = [],[]
        half = len(l)/2
        if len(l)%2==1: half +=1
        ans = 0
        for i in range(half):
        	p.append(lst[i])
        for i in range(half,len(l)):
        	q.append(lst[i])
        ans = (sum(p)-sum(q))*(sum(l))
        ans = ans%1000000007
        print ans