After several attacks by sharks this summer, namely in Florida and in Australia, but also in the Algarve, in southern Portugal, the local beach guardians are worried. They got together and decided to implement for the next beach season an automated shark detection system. Its a simple idea. They will rent airtime in a commercial satellite and take pictures of the seashore using submarine vision mode. In this operating mode, cameras are able to photograph underwater sea animals with incredible precision, even if the waters are not very clear.

The photos are transmitted by radio to the central computer of the beach guardians association, where they are analyzed. The main goal of such processing is to detect sharks, in order to issue an immediate shark alarm to the corresponding beach, if that is the case.

Processing is rather sophisticated, since not all sea animals are sharks: there are small fish (sardines), slightly larger fish (mackerel, salmons), large fish (groupers), sea mammals (dolphins, whales), reptiles (turtles). When seen from afar (from the satellite, that is), dolphins are similar to sharks, but the system must distinguish them or we risk raising false alarms just because a group of easygoing dolphins has approached the beach to play with the tourists.

Satellite photographs are digitally preprocessed and are now represented by a grid. In each square in the grid there is either a lower case letter (from `a' to `z') or there is nothing, i.e., the square is empty. Each sea animal is represented by a set of adjacent squares in the grid all bearing the same letter. Two grid squares are adjacent if they have one side in common.

All animals have a distinct rectangular shape, except sharks, as explained below. Single square animals (i.e., animals which fill one square only) are sardines. Two square animals (filling a 1 by 2 rectangle) are mackerels; longer animals with width 1 are salmons. Square animals larger than sardines are turtles (there can be 2 by 2, 3 by 3, etc., turtles). Groupers are rectangular with width 2 and length greater than 2. Dolphins are rectangular with width 3 and length greater than 3. Whales are rectangular with width 4 and length greater than 4. Finally sharks are similar to dolphins, having width 3, but their shape is not a rectangle. As a matter of fact, the tail fin for dolphins is horizontal and that is what gives dolphins a digitalized rectangular shape. Sharks, on the other hand, have a vertical tail fin, which is recognized by an extra square along the middle row of squares that represent the body of the shark.

All other shapes will have been erased during preprocessing, which guarantees that no unknown species can occur in the digitalized representation. As an example, consider the following photograph, where we can observe all the mentioned species.

b c f g h
b a a b c a j k y y y
b c a k y y y
c a y y y
z z z z z z u u u
z z z z z z s u u u
z z z z z z s s s u u u
t t t t s s s u u u
t t t t t s s s u u u
t t t t s s s u
h h
b b b b f f f h h
b b b b f f f h h
b b b b g g g g h h
b b b b g g g g p p p
b b b b g g g g p p p

On the upper left corner we see 3 mackerels. More to the right there are 2 salmons (one bigger than the other). Still more to the right, 6 beautiful sardines swim merrily. On the upper right corner, a giant turtle watches a ferocious shark, just below. There are 2 other smaller sharks and a large dolphin in the center rows. On the lower left corner a whale peacefully sits next to a second dolphin. On the lower right corner, 3 groupers wonder what they are doing in this crowded part of the ocean.

Your task is to write a program that processes a digitalized representation of a sea photograph in the format explained above and outputs the number of sardines, the number of mackerels, the number of salmons, the number of groupers, the number of turtles, the number of dolphins, the number of whales and the number of sharks present.


The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

The first line of input contains two numbers, L and C, representing the number of lines and the number of columns in the grid, respectively. Each of the remaining L lines contains exactly C characters, which are either lowercase letters or points. These lines represent the grid. A letter means that an animal or a part of an animal occupies the corresponding square. Points indicate that the corresponding square is empty.

The maximum number of lines and number of columns for the grid is 64.


For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

The output is just one line with 8 numbers: the number of sardines, the number of mackerels, the number of salmons, the number of groupers, the number of turtles, the number of dolphins, the number of whales and the number of sharks, as counted in the input. There is a single space between consecutive numbers and nothing else on the line (other than the end of line marker).

Sample Input 


16 12

Sample Output 

6 3 2 3 1 2 1 3

Pedro Guerreiro, MIUP'2001