H. Break the Walls
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A robot is placed on cell $$$(1,1)$$$ of an $$$n \times m$$$ grid and wants to reach the bottom-right corner at cell $$$(n, m)$$$. The grid contains obstacles represented by '#' and open cells represented by '.'. Cell $$$(1,1)$$$ is guaranteed to be open.

The robot can only move in two directions: down and right. In a regular step, the robot can move into an adjacent open cell. However, it can also break through an obstacle if both its previous step and current step are in the same direction. For instance, if there's an obstacle at $$$(x, y)$$$, the robot can move into it from $$$(x, y-1)$$$ only if it arrived here from $$$(x, y-2)$$$ in the previous step.

The goal is to reach the cell $$$(n, m)$$$ by minimizing the number of obstacles it breaks along the way or determining that it's not possible.

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

For each test case, the first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n\cdot m \leq 10^5$$$), the grid's dimensions.

Each of the next $$$n$$$ lines contains a string of $$$m$$$ characters ('.' or '#'), representing a row of the grid.

It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$

Output

For each test case, output a single integer — the minimum number of obstacles the robot needs to break to reach its goal or print $$$-1$$$ if it isn't possible to reach the goal.

Examples
Input
2
3 3
..#
..#
##.
4 4
.###
.#..
..##
#...
Output
1
0
Input
2
1 6
..##.#
3 1
.
#
.
Output
3
-1