Problem on Array

You are given an array of integers A1..N of N elements.

A function F(i) of A returns the largest index j of array A such that all Ak where i < k < j are smaller than both Ai and Aj. By convention, j = N if i = N. Consider the following example. Let A1..6 = {5, 2, 3, 6, 4, 5}; then, function F(i) for i = 1..6 will return {4, 3, 4, 6, 6, 6}. Notice that:

A function G(i) of A is defined as F(i) - i. Thus, in the previous example, G(i) for i = 1..6 is {3, 1, 1, 2, 1, 0}.

Your task in this problem is to output the largest G(i) and the sum of G(i) for all i given array A. In the previous example, the largest G(i) is 3, while the sum of all G(i) is 3 + 1 + 1 + 2 + 1 + 0 = 8.

As the sum of all G(i) can be very large, you should modulo the output by 1,000,000,007.

Input

Input begins with an integer: T (1 ≤ T ≤ 20) denoting the number of cases.

Each case contains the following input block: Each case begins with an integer N (1 ≤ N ≤ 500,000) denoting the array size. The next line contains N integers Ai (1 ≤ Ai ≤ 1,000,000,000) representing the array's element.

The sum of all N in input is no larger than 1,000,000.

Output

For each case, output in a line "Case #X: Y Z" where X is the case number (starts from 1), Y is the largest G(i), and Z is the sum of all G(i) modulo 1,000,000,007 for the respective case.

Examples

inputExample #1
4
6
5 2 3 6 4 5
5
1 2 3 4 5
5
5 4 3 2 1
4
100 130 125 147
output
Case #1: 3 8
Case #2: 1 4
Case #3: 1 4
Case #4: 2 4
explanation

Case 1: This is the example given in the problem statement.

Case 2: F(i) = {2, 3, 4, 5, 5}; G(i) = {1, 1, 1, 1, 0}.

Case 3: F(i) = {2, 3, 4, 5, 5}; G(i) = {1, 1, 1, 1, 0}.

Case 4: F(i) = {2, 4, 4, 4}; G(i) = {1, 2, 1, 0}.



End of Problem