Problem G
Walking to School

A Portraiture of the City of Philadelphia, by Thomas Holme. Public Domain.

Billy walks to school every day. He lives in a city with a regular grid of streets, with streets running east-west and north-south. However, some intersections are permanently blocked (for example, because of buildings or construction projects) so Billy cannot walk through them.

Billy always takes a path to school that is as short as possible. However, he insists on getting closer to his school with every step; if some portion of a path would require Billy to walk away from his school, he will not take that path (even if it is as short as possible). A path that gets closer to Billy’s school at every step is called monotonic.

Billy realizes that there may be many different monotonic paths which are equally short. Since he likes variety, he decides to take a different path to school every day. Help Billy figure out how many times he can walk to school before he has to repeat a path. Two paths are considered different as long as there is at least one segment that they do not share in common.

Input

Input begins with an integer $1 \leq T \leq 100$, indicating the number of test cases that follow. Each test case begins with a line containing two integers $w$ and $h$, with $1 \leq w, h \leq 100$. There follow $h + 1$ lines with $w + 1$ characters each, describing the grid of streets. Each character corresponds to an intersection. A period (.) indicates an open intersection, and an asterisk (*) indicates a blocked intersection. These are the only two characters which will occur in the grid.

Assume that Billy lives at the intersection in the lower-left corner, and his school is at the intersection in the upper-right corner. These two intersections will never be blocked.

Output

Output should consist of $T$ lines, one per test case. For each test case, print the number of distinct monotonic, shortest paths from Billy’s house to his school.

5
1 1
..
.*
3 3
....
.**.
....
...*
5 4
.*....
.*..*.
.*..*.
.*..*.
....*.
5 4
....*.
.*..*.
.*..*.
.*..*.
.*....
10 10
.*.*..*....
...........
..*.....**.
..*....***.
.**..*..*..
.....*.....
..****.....
........*..
..*....***.
..**..****.
...........

1
4
5
0
1045