Problem Statement

There is an $H \times W$ grid. Let $(i,j)$ denote the cell at the $i$-th row from the top and $j$-th column from the left.

Each cell is an empty cell or a wall cell, and this information is represented by $H \times W$ characters $S_{1,1},\dots ,S_{H,W}$. Cell $(i,j)$ is an empty cell if $S_{i,j}$ is ., and a wall cell if it is #.

Initially, Takahashi is at cell $(1,1)$. He can move to a cell adjacent to his current cell in one of the four directions (up, down, left, right) any number of times. However, he cannot move in the same direction twice in a row. Also, he cannot move to a wall cell or outside the grid.

Before starting to move, he can destroy zero or more wall cells to change them into empty cells. What is the minimum number of wall cells he needs to destroy to reach cell $(H,W)$? Under the constraints of this problem, it can be proved that there exists a way to destroy wall cells so that he can reach cell $(H,W)$.

You are given $T$ test cases; solve each of them.

Constraints

• $1 \le T \le 1000$
• $2 \le H, W \le 100$
• $S_{i,j}$ is . or #.
• $S_{1,1}$ and $S_{H,W}$ are ..
• The sum of $HW$ over all test cases is at most $3 \times 10^4$.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Each test case is given in the following format:

H W
S_{1,1}S_{1,2}\ldotsS_{1,W}
S_{2,1}S_{2,2}\ldotsS_{2,W}
\vdots
S_{H,1}S_{H,2}\ldotsS_{H,W}

Output

Output $T$ lines.

The $i$-th line should contain the minimum possible number of wall cells to destroy for Takahashi to reach cell $(H,W)$ for the $i$-th test case.