AT_abc424_d [ABC424D] 2x2 Erasing 2

$ H $ 行 $ W $ 列のマス目があり、各マスは白または黒に塗られています。 マス目の上から $ i $ 番目 $ (1\leq i\leq H) $ かつ左から $ j $ 番目 $ (1\leq j\leq W) $ のマスをマス $ (i,j) $ と表すことにします。 マス目の状態は $ H $ 個の、`.` と `#` のみからなる長さ $ W $ の文字列 $ S_1,S_2,\ldots,S_H $ によって与えられ、 $ S_i $ の $ j $ 文字目が `.` のとき、マス $ (i,j) $ が白く塗られていることを、`#` のときマス $ (i,j) $ が黒く塗られていることを表します。 高橋君はいくつか（ $ 0 $ 個でも良い）の黒く塗られたマスを白に塗り替えることで、 マス目が黒く塗られたマスのみからなる $ 2\times 2 $ の部分を持たないようにしたいです。 より厳密には、次の条件をみたすようにしたいです。 > $ 1\leq i\leq H-1 $ , $ 1\leq j\leq W-1 $ をみたす任意の整数の組 $ (i,j) $ について、 マス $ (i,j) $ , マス $ (i,j+1) $ , マス $ (i+1,j) $ , マス $ (i+1,j+1) $ のうち **少なくとも $ 1 $ つは白く塗られている** 。 高橋君が目標を達成するために、白く塗り替える必要のあるマスの個数の最小値を求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ $ \mathrm{case}_i $ は $ i $ 番目のテストケースを表す。 各テストケースは以下の形式で与えられる。 > $ H $ $ W $ $ S_1 $ $ S_2 $ $ \vdots $ $ S_H $

$ T $ 行出力せよ。 $ i $ 行目 $ (1\leq i\leq T) $ には、 $ i $ 個目のテストケースの答えを出力せよ。

### Sample Explanation 1 $ 1 $ つめのテストケースについて、マス目の最初の状態は、下図左のようになっています。 このマス目の黒いマスのうち、例えば下図右の番号が入っている $ 3 $ つのマスを白く塗り替えることで、条件をみたすようにできます。  最初の状態から $ 2 $ 個以下のマスを白く塗ることで条件をみたすようにすることはできないため、 $ 3 $ を $ 1 $ 行目に出力します。 $ 2 $ つめのテストケースについて、マス目は最初から条件をみたしています。 よって、 $ 0 $ を $ 2 $ 行目に出力します。 ### Constraints - $ 1\leq T\leq 100 $ - $ 2\leq H\leq 7 $ - $ 2\leq W\leq 7 $ - $ S_i $ は `.` と `#` のみからなる長さ $ W $ の文字列 - $ T,H,W $ は整数