Walking to School

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 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 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.

Sample Input 1 | Sample Output 1 |
---|---|

5 1 1 .. .* 3 3 .... .**. .... ...* 5 4 .*.... .*..*. .*..*. .*..*. ....*. 5 4 ....*. .*..*. .*..*. .*..*. .*.... 10 10 .*.*..*.... ........... ..*.....**. ..*....***. .**..*..*.. .....*..... ..****..... ........*.. ..*....***. ..**..****. ........... |
1 4 5 0 1045 |