Cho dãy số nguyên ~A[1], A[2], ..., A[N]~. Hãy thực hiện nhiệm vụ sau: chia dãy thành hai phần trái và phải, trong đó phần trái gồm ~N/2~ phần tử đầu tiên và phần phải gồm các phần tử còn lại. Tính tổng các phần tử của mỗi phần, cuối cùng tính và in ra tích hai tổng tìm được.

Đầu vào

Dòng đầu tiên của đầu vào chứa số nguyên ~T~ cho biết số bộ dữ liệu cần kiểm tra. Mỗi bộ dữ liệu bao gồm:

• Dòng đầu chứa số nguyên ~N~ cho biết số phần tử của dãy.
• Dòng thứ hai chứa ~N~ số nguyên cách nhau bởi dấu cách, là các phần tử của dãy.

Đầu ra:

• Ứng với mỗi bộ dữ liệu, chương trình của bạn in ra một dòng chứa kết quả của bài toán tương ứng với bộ dữ liệu đầu vào đó.

Ràng buộc:

• ~1<=T<=100;~ ~1<=N<=1000;~
• ~1<=A[i]<=100 (i=1...N)~;

Sample input:

3
4
1 2 3 4
3
4 5 6
1
2

Sample output:

21
44
0