AT_abc424_d [ABC424D] 2x2 Erasing 2

There is a grid with $ H $ rows and $ W $ columns, and each cell is painted white or black. Let us denote the cell at the $ i $ -th row from the top $ (1\leq i\leq H) $ and the $ j $ -th column from the left $ (1\leq j\leq W) $ by cell $ (i,j) $ . The state of the grid is given by $ H $ strings $ S_1,S_2,\ldots,S_H $ of length $ W $ consisting of `.` and `#`. If the $ j $ -th character of $ S_i $ is `.`, then cell $ (i,j) $ is white; if it is `#`, then cell $ (i,j) $ is black. By repainting some black cells (possibly zero) to white, Takahashi wants to make the grid have no $ 2\times 2 $ subgrid consisting only of black cells. More precisely, he wants to satisfy the following condition. > For any integer pair $ (i,j) $ with $ 1\leq i\leq H-1 $ and $ 1\leq j\leq W-1 $ , among cells $ (i,j) $ , $ (i,j+1) $ , $ (i+1,j) $ , and $ (i+1,j+1) $ , **at least one is white**. Find the minimum number of cells that need to be repainted white in order for Takahashi to achieve his goal. You are given $ T $ test cases; answer each of them.

The input is given from Standard Input in the following format: > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ $ \mathrm{case}_i $ represents the $ i $ -th test case. Each test case is given in the following format: > $ H $ $ W $ $ S_1 $ $ S_2 $ $ \vdots $ $ S_H $

Output $ T $ lines. On the $ i $ -th line $ (1\leq i\leq T) $ , output the answer for the $ i $ -th test case.

### Sample Explanation 1 For the first test case, the initial state of the grid is as shown in the left figure below. By repainting, for example, the three cells with numbers in the right figure below from black to white, the condition can be satisfied.  It is impossible to satisfy the condition by repainting two or fewer cells from the initial state, so output $ 3 $ on the $ 1 $ -st line. For the second test case, the grid already satisfies the condition from the beginning. Thus, output $ 0 $ on the $ 2 $ -nd line. ### Constraints - $ 1\leq T\leq 100 $ - $ 2\leq H\leq 7 $ - $ 2\leq W\leq 7 $ - Each $ S_i $ is a string of length $ W $ consisting of `.` and `#`. - $ T,H,W $ are integers.