Problem Description

You are given a sequence of
N
integers.



You should choose some numbers(at least one),and make the product of them as big as possible.



It guaranteed that **the absolute value of** any product of the numbers you choose in the initial sequence will not bigger than
263−1.

 

Input

In the first line there is a number
T
(test numbers).



For each test,in the first line there is a number N,and
in the next line there are N
numbers.



1≤T≤1000

1≤N≤62



You'd better print the enter in the last line when you hack others.



You'd better not print space in the last of each line when you hack others.

 

Output

For each test case,output the answer.

 

Sample Input

1

3

1 2 3

 

Sample Output

6

水题一枚！可是坑了我两三次，结果没注意输入的数可以是long long 型wa了好几次~~

//题意：给你若干个整数，让你挑选若干数字使得其乘积最大

//算法分析：将这些数字都进行分类，正数、负数、零分别放在不同的一个数组中，然后再进行讨论！讨论负数时候，若为奇数个，去掉最大的那个，留下的相乘即可！偶数个直接相乘 

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

#include <algorithm>

#include <stack>

using namespace std;

typedef long long int LL ;

int main() {

	int t;

	cin >> t;

	while (t --) {

		int n;

		cin >> n;

		LL a[100];

		LL b[100], c[100];

		memset(a, 0, sizeof(a));

		memset(b, 0, sizeof(b));

		memset(c, 0, sizeof(c));

		int num1 = 0, num2 = 0;

		int flag = 0;

		for (int i  = 0; i<n; i++) {

			cin >> a[i];

			if (a[i] > 0)

				b[num1++] = a[i];

			else if (a[i] < 0)

				c[num2++] = a[i];

			else

				flag ++ ;

		}

		sort(c, c+num2);

		LL res = 1;

		if (num1 == 0) {

			if (num2 == 0)

				cout << 0<< endl;

			else if(num2 == 1) {

				if (flag == 0)

					cout << c[0] << endl;

				else

					cout << 0<< endl;

			}

			else {

				if (num2 %2 == 0) {

					for (int i = 0; i<num2; i++)

						res *= c[i];

				}

				else {

					for (int i = 0; i<num2-1; i++)

						res *= c[i];

				}

				cout << res << endl;

			}

		}

		else {

			for (int i = 0; i<num1; i++)

				res *= b[i];

			if (num2 %2 == 0) {

				for (int i = 0; i<num2; i++)

					res *= c[i];

			}

			else {

				for (int i = 0; i<num2-1; i++)

					res *= c[i];

			}

			cout << res << endl;

		}

	}	

	return 0 ;

} 
有坑跳才会进步！