Given an array A having n elements, let X be the maximum sum of any contiguous sequence in the array. How many contiguous sequences in A sum up to X?

Input

The first line contains T the number of test cases. There follow 2T lines, 2 for each test case. The first line contains the n, the number of elements in the array. The second line contains n space separated integers Ai.

Output

Output T lines, one for each test case. On each line, output two space separated integers; the maximum sequence sum, and the number of sequences which obtain this maximum sum.

Example

Input:
2
3
-1 -1 -1
4
2 0 -2 2

Output:
-1 3
2 4

Constraints

1 <= T <= 35
1 <= n <= 100000
-1000 <= Ai <= 1000