Sauron's army is trying to take over Middle Earth and you are assigned the task of calculating the strength of his army. Middle Earth can be visualized as a 2-D grid. A cell in this grid has an 'x' if it is occupied by the orcs of Sauron's army and a cell has a '.' if it is occupied by a soldier of Gondor's army.
A squad of Sauron's army is defined as a maximally connected component of 'x' cells. Two 'x' cells are connected if they are horizontally, vertically or diagonally adjacent. A squad of Gondor's army is defined as a maximally connected component of '.' cells. Two '.' cells are connected if they are horizontally or vertically adjacent.
A squad A reinforces squad B if A and B are different and, if you start walking from any point of squad B, you won't be able to walk out of squad A (you can walk only horizontally and vertically, but not diagonally). A squad that reinforces no other squad is said to have strength 0. A squad has strength S+1 if it reinforces one or more squads and the maximum strength of a contained squad is S.
Given the 2-D grid, you have to print an array of int[] where the ith element denotes how many squads of Sauron's army have strength 'i'. The numbers must be space separated. The array must contain exactly (k+1) elements, where k is the maximum strength of any squad in the grid.
INPUT FORMAT
First line contains the number of test cases T. For each test case, the first line contains 2 integers N and M denoting the number of rows and number of columns of the grid respectively. The next N lines contain M characters each and each character being either 'x' or '.', both in lowercase.
OUTPUT FORMAT
Print T lines where each line is the answer for that test case and contains (k+1) space separated integers denoting the number of squads of each strength from 0 to k.
CONSTRAINTS
1<=T<=20
1<=N,M<=50
In the first sample, the inner 'X' has strength 0 because there is no other squad inside it and the outer squad has strength 1 because it reinforces one squad and the maximum strength of a squad it reinforces is 0.