You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Time Limit: 1.0 s

Memory Limit: 256.0 MB

Description

Roy has a special array A of length N, where every element is either -1, 0, or 1. The length of the array, N, is always divisible by 3. Roy starts with a score of 0 and must repeatedly perform the following operation until the array becomes empty:

• Select three distinct indices i, j, k (i ≠ j ≠ k) from the array.
• Remove the elements A[i], A[j], and A[k] from the array.
• Add the product of the selected elements A[i] × A[j] × A[k] to his score.

Roy wants to maximize his final score after performing these operations optimally. Your task is to determine the maximum score Roy can achieve.

Input

• The first line contains a positive integer T,(1 ≤ T ≤ \(10^4\)) the number of test case.
• In each test case, the first line contains a single integer N (3 ≤ N ≤ \(2 * 10^5\)), representing the length of the array A. N is guaranteed to be divisible by 3.
• The second line contains N integers, the elements of the array A, where each element is either -1, 0, or 1.

Sum of N overall test case doesn't exceed \(2 * 10^5\).

Output

In each test case, output a single integer: the maximum final score Roy can achieve if he performs the operations optimally.

Sample

2
6
-1 -1 1 1 1 -1 
3
1 0 -1

0
0