G. Dinnerbone and Array
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Today is Dinnerbone's birthday! For their birthday present, Grumm (Dinnerbone's best friend) decides to gift Dinnerbone an array $$$A$$$ of length $$$N\ (1\leq N \leq 15)$$$. This array is very special to Dinnerbone because each $$$\lvert{A_i}\rvert\leq 10^{4}$$$. Given that Dinnerbone can select any strict subset $$$S$$$ of the array, calculate the maximum and minimum possible values of $$$$$$\left(|S|\cdot (-1)^{|S|}\cdot \sum_{x \in S} x^3\right)$$$$$$

Input

The first line contains $$$T\ (1\leq T\leq 1000)$$$, the number of test cases.

Each test case will start with $$$N\ (1\leq N \leq 15)$$$, the length of the array. The next line contains an array $$$A$$$ of length $$$N$$$, where the $$$i$$$-th element is $$$A_i$$$.

Output

For each case, print the minimum and maximum value, separated by a space and ending with a newline.

Example
Input
1
5
-14 12 -11 8 8
Output
-12204 10689