Problem: Tanmay is a legendary spammer - everyone in the spamming world knows and admires his abilities to spam anyone, anytime, anywhere. He decided to guide one of his mentors, named Arjit, as part of the Apex body of spamming. 

Tanmay has no doubts on his skills of teaching and making his mentor, Arjit, learn about the art of spamming. But, he surely has serious doubt on Arjit's skills of learning, implementing and executing whatever he has decided to teach him as part of the syllabus of spamming.

Tanmay has sent Arjit to test his skills, but he's getting extremely anxious about the performance of his mentee. So, to calm himself down he asks you to help him find out the maximum and the minimum productivity attained by Arjit in his travel.

Arjit has the option to visit N Facebook groups - where every Facebook group has some potential which can be negative, zero or positive. Now, he can decide to visit a group if he wants to or not. (Depending on the lessons taught to him by the great master!) The total productivity attained by Arjit is the product of all the groups he decides to visit.

Given the values of all the groups, find out the maximum and minimum spamming potential he can achieve and let Tanmay know about it, so that he calm himself down.

Input format:
The first line contains an integer, T, denoting the number of test cases. Each line of the test case contains an integer, N, denoting the size of the array. The next line contains N integers, denoting the value of the numbers in the array.

Output format:
Print the maximum product you can obtain followed by the minimum product. A space separates both these outputs. Answer to each test case is on a new line.  

Constraints:
1 ≤ T ≤ 500
1 ≤ N ≤ 18
-10 ≤ Ni ≤ 10  

Note:
In some cases only one element may be considered for minimum or maximum product.
If the array is (1, 2, 3), minimum product is 1 whereas maximum product is 6.
When the array is (-1, -2), minimum product is -2 whereas maximum product is 2.

SAMPLE INPUT
2
4
1 0 2 10
3
0 0 0

SAMPLE OUTPUT
20 0
0 0

Explanation

In the first test case, the maximum product is the product of all the numbers except 0, whereas the minimum product is the product of all numbers including 0.
In the second test case, the maximum and minimum product both are 0 as 0 is the only available number.

Solution (in PYTHON):

Solution:
import sys
T = int(raw_input())
for k in range(T):
    N = int(raw_input())
    x = [int(y) for y in raw_input().split()]
    x.sort()
    max_z,min_z,max_p,min_p,max_n,min_n=-1000000,1000000,-1000000,1000000,-1000000,1000000
    pos_l,neg_l,zero_l = [],[],[]
    for i in range(N):
        if x[i] > 0:
            pos_l.append(x[i])
        elif x[i] == 0:
            
            zero_l.append(0)        
        else:
            neg_l.append(x[i])

    neg_l.sort(reverse=True)
            
    if len(pos_l) > 0:
        max_p = 1
        for i in pos_l:
            max_p*=i
        min_p = pos_l[0]

    if len(zero_l)>0:
        max_z,min_z = 0,0

    if len(neg_l)>0:
        
        if len(neg_l)>1:
            n = len(neg_l)
            if n%2 == 0:
                max_n=1
                min_n=1
                for i in neg_l:
                    max_n*=i
                for j in neg_l[1:]:
                    min_n*=j
            else:
                min_n = 1
                max_n = 1
                for i in neg_l:
                    min_n*=i
                for j in neg_l[1:]:
                    max_n*=j
        else:
            max_n = neg_l[0]
            min_n = neg_l[0]


    ans_max = -1000000                
    if max_n>0 and max_p>0:
        ans_max= max_n*max_p

    elif max_n<0:
        ans_max = max(max_p,max_n,max_z)
        
    elif max_n>0 and max_p==0:
        ans_max = max_n

    ans_M= max(ans_max,max_z,max_p,max_n)

    ans_min = 1000000
    if min_n<0 and max_p>0:
        ans_min = min_n*max_p

    elif min_n<0 and max_p==0:
        ans_min = min_n
        
    elif min_n>=0 and min_p>=0:
        ans_min = min(min_n,min_p,min_z)

    ans_m  = min(ans_min,min_n,min_p,min_z)

    print ans_M,ans_m