DCEPC11A - A Mushroom Adventure

no tags 

Nancy was planning to make her favorite dish “Masala Corn Mushroom” and she needs to collect a lot of mushrooms for making this dish. The mushrooms grow in an N × M field and she wants to collect all the mushrooms present in the field.

A Mushroom is present in only some of the cells in the field. She is standing in the top left corner of the field and needs to go to the bottom right corner, collecting mushrooms on the way. As she is hungry, she will use the shortest possible way to reach her destination. But before making the trip, she wants your help to know whether she can collect all the mushrooms present in the field or not.

Input

First line contains T, the number of test cases.

The first line of each test case contains N and M, the length and width of the field.

The next N lines each contain M characters, either ‘.’ or ‘*’, where ‘.’ represents an empty cell and ‘*’ represents a mushroom.

Output

Output “YES” if it is possible for Nancy to collect all the mushrooms, otherwise output “NO”.

Constraints

1 <= T <= 10

1 <= N, M <= 500

Example

Input:
2
2 2
.*
*.
4 3
.*.
.**
...
..*

Output:
NO
YES


Added by:dce coders
Date:2013-10-01
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C C++ 4.3.2 CPP JAVA
Resource:Own Problem