AT_arc214_f [ARC214F] Unpredictable Moves

$ H \times W $ のマス目があります。上から $ i $ 行目、左から $ j $ 列目のマスを $ (i,j) $ で表します。 各マスは空きマス・壁マスのいずれかであり、その情報は $ H \times W $ 個の文字 $ S_{1,1},\dots ,S_{H,W} $ によって表されます。 マス $ (i,j) $ は、 $ S_{i,j} $ が `.` のとき空きマス、`#` のとき壁マスです。 はじめ、高橋君がマス $ (1,1) $ にいます。 高橋君は、今いるマスと上下左右のいずれかの方向に隣接するマスに移動することを好きな回数行うことが出来ます。 ただし、 **$ 2 $ 回続けて同じ方向に移動することは出来ません**。 また、壁マスやマス目の外に移動することも出来ません。 高橋君は移動を開始する前に $ 0 $ 個以上の壁マスを破壊して空きマスに変化させることが出来ます。 高橋君がマス $ (H,W) $ に辿り着くためには、最小でいくつの壁マスを破壊する必要があるでしょうか？ この問題の制約下において、マス $ (H,W) $ に辿り着くことが出来るように壁マスを破壊する方法が存在することは証明出来ます。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めて下さい。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ 各テストケースは以下の形式で与えられる。 > $ 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} $

$ T $ 行出力せよ。 $ i $ 行目には $ i $ 番目のテストケースについて、高橋君がマス $ (H,W) $ に辿り着くために破壊する壁マスの個数としてありうる最小値を出力せよ。

### Sample Explanation 1 $ 1 $ つ目のテストケースについて、下図のように $ 2 $ 個の壁マスを破壊することでマス $ (H,W) $ に辿り着く事が出来ます。  左側は破壊する壁マスの例を表しており、右側は移動経路の例を表しています。 必ずしも移動回数を最小化する必要がない点や、同じマスに $ 2 $ 回以上訪れても良い点に注意して下さい。 $ 2 $ つ目のテストケースについて、壁マスを $ 1 $ つも破壊せずにマス $ (H,W) $ に辿り着くことが出来ます。 ### Constraints - $ 1 \le T \le 1000 $ - $ 2 \le H, W \le 100 $ - $ S_{i,j} $ は `.` または `#` - $ S_{1,1} $ および $ S_{H,W} $ は `.` - 全てのテストケースにおける $ HW $ の総和は $ 3 \times 10^4 $ 以下