Server Time: Wed Feb 26, 2020 12:46 pm
Welcome ( logout
H - The Great Escape
PDF (English) Ranklist
Time Limit: 5 second(s) Memory Limit: 32 MB

Walter White finally discovered the medicine for a dangerous disease. That's why he is in danger, because some people are targeting him to get the formula. So, now he and his co-workers have to leave the city.

Assume that the city can be modeled as an M x N grid, where a cell containing a '*' means that a co-worker lives in that place, a cell containing a '.' means it's empty.

So, Walter informed all of them by phone to leave the city at once and he has laid down a rule that no one will cross path in their way out of the city. Since if two or more persons meet at same cell (even in the boundary cells), there is a big possibility that they all might get caught. Walter doesn't want that, so he needs to know whether all of them can get out of the city. So, he asked you to help him.

For simplicity, assume that if one person reaches any of the border cells of the grid, he is considered to be out of the city. And from any cell, a person can move only to its four adjacent cells (north, south, east or west).

a1.png

a2.png

Fig 1: Position of the persons

Fig 2: Escape Paths

For example, for the given 7 x 6 grid, the colored circles show the position of the persons who are escaping (fig 1). And a feasible solution is shown in fig 2.

Input

Input starts with an integer T (≤ 20), denoting the number of test cases.

Each case starts with a line containing two integers M and N (1 ≤ M, N ≤ 100). Each of the next M lines contains N characters denoting the map. Each characters is either '.' or '*'. Total number of persons in a map will be at most 2*(M+N).

Output

For each case, print the case number and 'yes' if it's possible for them to get out of the city maintaining the restrictions. Otherwise print 'no'.

Sample Input

Output for Sample Input

3

7 6

..*...

.*.*..

..*.*.

***..*

.....*

..**..

....*.

4 10

***..***.*

*.**.***.*

..*..*..**

.**.*.*.**

4 10

***..***.*

*.**.***.*

..*..*...*

.**.*.*.**

Case 1: yes

Case 2: no

Case 3: yes

 


Problem Setter: Jane Alam Jan
Special Thanks: S. M. Ijaz-ul-Amin Chowdhury
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan