Input

The first line contains the number of test cases N. Each test case consists of a line with two numbers H and W, which are the height and the width of the map. Then follow H lines with a string of W letters. Those letters will only be lowercase letters from "a" to "z".

Output

For each test case print "World #n", where n is the number of the test case. After that print a line for each language that appears in the test case, which contains the language, a colon, a space and the number of states, where that language is spoken. These lines have to be ordered decreasingly by the number of states. If two languages are spoken in the same number of states, they have to appear alphabetically, which means language "i" comes before language "q", for example.

Sample Input

2

4 8

ttuuttdd

ttuuttdd

uuttuudd

uuttuudd

9 9

bbbbbbbbb

aaaaaaaab

bbbbbbbab

baaaaacab

bacccccab

bacbbbcab

bacccccab

baaaaaaab

bbbbbbbbb

Sample Output

World #1

t: 3

u: 3

d: 1

World #2

b: 2

a: 1

c: 1