using System;

public class Program

{

    public static void Main()

        {

            /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution */

​

            //Console.WriteLine("Enter the number of case:");

            int Numcase = Convert.ToInt32(Console.ReadLine());

​

            int[,] output = new int[Numcase, 2];

​

            for (int i = 1; i <= Numcase; i++)

            {

                //Console.WriteLine("Enter the length of array for case " + i);

                int len = Convert.ToInt32(Console.ReadLine());

                string input;

                string[] splited;

                int[] inputary = new int[len];

                //bool error = false;

                //do

                //{

                    //error = false;

                    //Console.WriteLine("Enter the array (seperated by space):");

                    input = Console.ReadLine();

                    splited = input.Trim().Split(' ');

​

                //    if (splited.Length != len)

                //    {

                //        Console.WriteLine("Array length mismatch...please ReEnter the array");

                //    }

                //    else

                //    {

                    for (int j = 0; j < splited.Length; j++)

                    {

                        //try

                        //{

                            inputary[j] = Convert.ToInt32(splited[j]);

                        //}

                        //catch (Exception e)

                        //{

                        //    error = true;

                        //    Console.WriteLine("Invalid input array.. please ReEnter the array");

                        //    break;

                        //}

                    }

                //    }

                //} while (splited.Length != len || error);

​

                //Find the contiguous and non contiguous sum and assign to output array

                output[i - 1, 0] = ContiguousSum(inputary);

                output[i - 1, 1] = NonContiguousSum(inputary);

​

            }

            //Console.WriteLine("Done\n Output  is:");

​

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

            {

                for (int j = 0; j < 2; j++)

                {

                    Console.Write(output[i, j] + " ");

                }

                Console.Write("\n");

            }

            Console.ReadLine();

        }

​

        private static int ContiguousSum(int[] inputArray)

        {

            //try

            //{

                int maxSum = inputArray[0];

​

                for (int i = 0; i < inputArray.Length; i++) //Set starting node

                {

                    for (int j = 1; j <= inputArray.Length - i; j++) //set num of elements in addition 

                    {

                        int k = 0;

                        int tempsum = 0;

                        while (k < j)

                        {

                            tempsum += inputArray[i + k];

                            k++;

                        }

                        if (tempsum > maxSum)

                            maxSum = tempsum;

                    }

                }

                return maxSum;

            //}

            //catch (Exception ex)

            //{

            //    return 0;

            //}

        }

​

        private static int NonContiguousSum(int[] inputArray)

        {

            int maxNsum = inputArray[0];

            //try

            //{

                int powerSetLen = FindPowerSetLen(inputArray.Length);

                for (int i = 1; i < powerSetLen; i++)

                {

                    int tempsum = 0;

                    for (int j = 0; j < inputArray.Length; j++)

                    {

​

                        if ((i & (1 << j)) != 0)

                        {

                            tempsum += inputArray[j];

                        }

                    }

                    if (tempsum > maxNsum)

                        maxNsum = tempsum;

                }

            //}

            //catch (Exception ex)

            //{

            //    return 0;

            //}

            return maxNsum;

        }

​

        private static int FindPowerSetLen(int n)

        {

            int ans = 1;

            for (int i = 1; i <= n; i++)

            {

                ans = ans * 2;

            }

            return ans;

        }

}