Arithmatic and geometric Progressions are 2 of the well known progressions in maths.

Arithmatic progression(AP) is a set in which the difference between 2 numbers in constant. for eg, 1,3,5,7,9 .... In this series the difference between 2 numbers is 2.

Geometric progression(GP) is a set in which the ratio of 2 consecutive numbers is same. for eg, 1,2,4,8,16.... In this the ratio of the numbers is 2.

What if i take 1 AP and 1 GP series and write the numbers together in one series and jumble them... For eg

1,16,4,7,8,1,2,5,9,3.. (This series has AP -    1,3,5,7,9  and GP -     1,2,4,8,16.).

Now ur task is to separate out the 2 series and print the Sum of both the series.

Input

First line of the input will have a value 't' - Number of test cases. then the test cases follow.

first line of each test case has number 'n' -- number of elements in the jumbled series. (n<100)

Second line of each test case has n numbers of the series..

Output

For each test case print one line having 2 numbers, Sum of AP & Sum of GP ..

Example

Input:

1
10
1 16 4 7 8 1 2 5 9 3

Output:

25 31

NOTE: all the numbers will be less than 2^64 
If any number is part of both AP and GP . Consider it to be part of AP