315. Meeting Point

Problem Statement:
Unfortunately, Abdelrahman Mostafa (the regional director of operations in the ACPC) was unable to travel to the ACPC 2013 due to personal circumstances. Therefore, Mohamed Fouad, the Executive Director of Arab Region, was the one to lead the operations team in the ACPC. One of the main problems was how he (Mohamed Fouad) was going to communicate with the runners during the five hours of the contest. Therefore, he decided to divide the contest floor to a grid of N rows by M columns each cell of this grid may be:

1. '.', which means that the cell is empty.

2. 'T', which means that the cell contains a team.

3. 'H', which means that the cell contains a runner who can move horizontally only to neighboring empty cells in the same row.

4. 'V', which means that the cell contains a runner who can move vertically only to neighboring empty cells in the same column.

You are to help Mohamed Fouad to know the meeting point that he can select to meet the maximum number of runners without violating that horizontal runners move horizontally only, vertical runners move vertically only, and runners cannot pass through cells containing teams as the runners tend to disconnect the jammed power and network cables -unintentionally - which interrupts the contestants.

Input Format:
Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1 ≤ T ≤ 100).

The first line of each test case will contains two integers N and M where N is the number of rows and M is the number of columns (1 ≤ N, M ≤ 200).

Followed by N * M Matrix represents the gird, each cell in the matrix will contain one of the following [ . , T , H , V ] as described in the problem statement.

- Note that there will be at least one runner ( at least 1 H or 1 V )

Output Format:
For each test case, print a single line containing "Case n:" (without the quotes) where n is the test case number (starting from 1) followed by a space then three integer numbers A, I, J where A is maximum number of runners could meet in one cell and I is the row number of this cell ( 0-based ) and J is the column number of this cell ( 0-based ).

If there is more than one cell contains the same answer, output the cell with the largest I. If the tie still stand, output the cell with the largest J.

- Note that the meeting point could not be in a cell containing 'T'.

Sample Input:
3 3 3 .T. TV. H.H 5 5 .HT.V V.V.T T..TV .THH. V.VHV 2 4 HHTH TTTT

Sample Output:
Case 1: 3 2 1 Case 2: 4 3 4 Case 3: 2 0 1

 Added by: ahmed_aly Added at: 2014-10-25 09:00:00 UTC Time Limit: 3 seconds Partial score: No Source: ACM Oman Collegiate Programming Contest 2014