RK and RG are best friends. They are very particular in maintaining their Swag Level. Now, RK and RG travel to a mysterious place. There they found n Swag Traits.

A Swag Trait is defined as an array of positive integers of some given size.

Now, RK and RG decided to increase their Swag Level by playing a game in which they take turns and RK always moves first. In his turn, RK removes an integer from the beginning of any non-empty SWAG Trait, and in RG’s turn, he removes an integer from the end of any non-empty SWAG trait. They keep on playing until all the SWAG traits are empty.

Both of them want to maximize their SWAG Level. Considering both of them play optimally, you have to output two integers, the Swag Level of both RK and RG.

SWAG Level of a person is defined as the sum of the integers removed by the person from the SWAG Traits.

INPUT:

First line contains an integer T (1 ≤ T ≤ 100) representing the number of Test cases.

Each Test case contains an integer n (1 ≤ n ≤ 100), the number of SWAG Traits.

Next n lines contain description of each SWAG Trait:

First integer in each line is ki (1 ≤ ki ≤ 100) the size of ith SWAG Trait. Next ki integers are the elements of the SWAG Trait. Each element is a positive integer less than or equal to 1000.

Output:

For each test case, output two space separated integers: the SWAG level of RK and the SWAG level of RG, considering they played optimally.