Server Time: Mon Oct 26, 2020 6:13 am
Welcome ( logout
E - Game
PDF (English) Ranklist
Time Limit: 2 second(s) Memory Limit: 32 MB

Mirko and Slavko are playing chess like game. The game is played on a non-standard chess board sized R rows by C columns. Each player starts with some number of chess kings. In chess kings can move from their current field to any of the 8 neighboring fields.

Player spread is defined as the complete sum of distances between all pairs of pieces of the given player. The distance between two pieces is the smallest number of moves required for both pieces to reach the same field.

No actual moves are performed when calculating the distance and as such enemy pieces do not influence the result.

Mirko knows that the spread is a vital piece of strategic information and would like you to make him a program that will calculate both his and Slavko's spread.

Input

Input starts with an integer T (≤ 10), denoting the number of test cases. Each case starts with a blank line.

The first line of input contains two integers R and C (1 ≤ R, C ≤ 1000), number of rows and columns. Next R lines contain C characters each. Character 'M' denotes Mirko's piece, 'S' Slavko's piece and '.' denotes an empty field. There is at least one piece per player on the board. Otherwise the game would be over.

Output

Output should contain two integers. The first integer is the spread of Mirko's and the second Slavko's pieces.

Sample Input

Output for Sample Input

3

 

2 3

SMS

MMS

 

2 3

S.M

M..

 

4 5

M....

..S.M

SS..S

.M...

3 5

2 0

10 13

 


Problem Source: COCI 2009/2010, Contest 7
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan