Server Time: Mon Oct 26, 2020 7:12 am
Welcome ( logout
C - Explosions
PDF (English) Ranklist
Time Limit: 2 second(s) Memory Limit: 32 MB

When it comes to trams, a lot of people are civilized individuals who know how to behave in one. However, there are always those few who upon spotting a place to sit will run towards it in supersonic speeds. If they spot more than one place, they always try the closest one first.

Problems arise when two or more such individuals aim for the same spot. If one of them is the closest, he or she will sit, and others won't even attempt to move in and instead turn their attention to the next closest spot. If however they are all equally close, they will all run to the seat resulting in a massive explosion that usually ends with complete destruction of both them and the seat.

You are given a description of one tram. It is represented as a table with R rows and C columns. The rude passengers are marked with the letter 'X'. Empty seats are marked with 'L' and the tram floor is marked with '.'. Note that although there are other passengers, the force projected by these idiots is more than enough to simply walk through them.

Distance between two cells is the Euclidean distance between their centers. Write a program that will determine the number of explosions which will take place before all people are seated, or destroyed, or they run out of chairs.


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 (1 ≤ R ≤ 100) and C (1 ≤ C ≤ 100), number of rows and columns. The next R lines contain C characters each, '.', 'X' or 'L'. There will always be at least one character 'X' and at least one 'L' in the input. Also, there will be no two 'L' characters such that they are both equally distant to some 'X'.


Output should contain the number of explosion for the given layout.

Sample Input

Output for Sample Input



4 4






4 4






7 7












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