ADASEA - Ada and Island

Ada the Ladybug just read a book from famous author Dobsonfly Daffoedil. It is about Robinson's Cicada, who was flying over sea. Suddenly she had an accident and fell to island below her. Luckily the island was big enough, so she could recover and fly home till Friday night... or something like that.

As Ada was reading through the book, she fell asleep and started dreaming. She was thinking about how lucky the Cicada was, that she fell into such big island. She could have fallen into a smaller one or even to sea.

It keeps bugging her, so she has asked you to tell her the expected size of island, the Cicada will fall to (considering equal probability for all coordinates). Since Ada is not friend of floating point numbers, she wants the answer in some "nice" form.

Island is considered to be union of any '#' characters, which share side.

Input

The first line contains an integer T, the number of test-cases.

Each test-case begins with two integers N, M, 1 ≤ N, M ≤ 1000

Afterward N lines follow, with M characters. Each of the characters is either '#' (island) or '~' (sea).

Output

For each test-case print the expected size of island. Output it as p / q, where p and q has no common divisor. If p / q can be printed as an integer (not as fraction), do so!

Example Input

5
3 4
~~~~
~~~~
~~~~
3 3
#~~
##~
~~~
4 5
#~##~
#~~~#
~~~~#
####~
1 1
#
4 4
~~~~
##~~
~##~
##~~

Example Output

0
1
7 / 5
1
9 / 4

Added by:Morass
Date:2017-02-10
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2024-09-10 18:03:27
It might give TLE. Try to avoid recursion
2022-11-01 22:37:02
DFS+GCD
2022-10-26 04:23:47
The p/q shows that the final answer may not be an integer so print the output as a fraction term where p is the numerator and q is the denominator of that fraction with the condition gcd(p,q)=1
2022-06-24 22:03:56 David
I get it now! The "~" character is waving and is the sea! Funny.
Unfortunately, Java is too slow now. 1.1 sec on old laptop for 200 random mazes (size is random value from 10 to 1000) where probability of "#" at a particular coordinate is .5.
2022-03-20 11:58:53
anyone can explain for me what p / q is?
i need helpppp :D
2021-08-14 11:57:32
If you are getting error use long long and check the gcd function
2020-11-03 16:31:10
there is space between slash(/) and p and q.
2020-09-05 22:27:50
dfs jindabad
2020-05-03 12:52:07
So many if cases at the end lol
2019-10-07 09:31:56
[Spoiler] DSU!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.