AT_arc214_f [ARC214F] Unpredictable Moves

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.

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} $ $ \ldots $ $ S_{1,W} $ $ S_{2,1} $ $ S_{2,2} $ $ \ldots $ $ S_{2,W} $ $ \vdots $ $ S_{H,1} $ $ S_{H,2} $ $ \ldots $ $ S_{H,W} $

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.

### Sample Explanation 1 For the first test case, Takahashi can reach cell $ (H,W) $ by destroying two wall cells as shown below.  The left side shows an example of wall cells to destroy, and the right side shows an example of a movement path. Note that it is not necessary to minimize the number of moves, and it is allowed to visit the same cell more than once. For the second test case, he can reach cell $ (H,W) $ without destroying any wall cells. ### 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 $ .