Both Alice and Bob likes to count the character in string. But Alice doesn't like to count the same character twice in a string. So, she doesn't count the same character twice while counting the characters in any particular string.

A string of length N is given to them. Then they started to count the characters for each of the substring. You need to find the total count of both Alice and Bob that they calculated. In other words, you need to calculate — 
            • Total count of Alice = ∑A(x) 
            • Total count of Bob = ∑B(x)
            where x denotes a string which is a substring of the given string, S. Also, A(x) and B(x) counts the
            character for Alice and Bob respectively in string, x.

Let's define a substring of string S is a string that consists of some consecutive characters from string S. For example, strings "ab", "abc" and "b" are substrings of string "abc", while strings "acb" and "ac" are not. Any string is a substring of itself.

Input starts with an integer T — denoting the number of test cases.
The first line of each test case contains one integer N — the length of the string S. The next line contains the string S of length N consisting only of lowercase Latin letters.

T (1 ≤ T ≤ 10000)
N (1 ≤ N ≤ 200000)
The sum of N over all test cases doesn't exceed 400000.

In the first line of every test case, print the output just like the sample output "Case #Z: P Q" (without the quotes) — where Z is the case number. P and Q denotes the total count of Alice and Bob respectively).

Input copy	Output copy
3 3 aba 1 c 2 pp	Case #1: 9 10 Case #2: 1 1 Case #3: 3 4