AT_bogosortcontest_div2_i Moving Super King

$ H $ 行 $ W $ 列のグリッドがあります。上から $ i $ 行目、左から $ j $ 列目のマスを $ (i,j) $ と表します。 はじめ、各マスには石が置かれているか、何も置かれていないかのいずれかです。グリッドの状態は $ H $ 個の文字列 $ S_1,S_2,\ldots,S_H $ で表され、 $ S_i $ の $ j $ 文字目が `#` のときマス $ (i,j) $ には石が置かれており、`.` のときマス $ (i,j) $ には何も置かれていません。 Alice は、はじめに何も置かれていないマスを $ 1 $ つ選び、そのマスに「Super King」を置きます。その後、Bob から始めて、Alice と Bob は交互に手番を行います。 Bob の手番では、次の操作を行います。 - 石も Super King も置かれていないマスを $ 1 $ つ選び、そこに石を置く。 Alice の手番では、次の $ 2 $ つの操作のうちいずれか $ 1 $ つを行います。 - 石も Super King も置かれていないマスを $ 1 $ つ選び、そこに石を置く。 - Super King が現在マス $ (i,j) $ にあるとする。石も Super King も置かれていないマス $ (x,y) $ であって、 $ \max(|i-x|,|j-y|) \le K $ を満たすものを $ 1 $ つ選び、Super King を $ (x,y) $ に移動させる。移動前に Super King があったマス $ (i,j) $ には何も置かれていない状態になる。 自分の手番で可能な操作が存在しないプレイヤーは敗北し、もう一方のプレイヤーが勝利します。 Alice と Bob はともに最適に行動します。Alice が Super King の初期位置として選ぶことで、Alice が勝利できる空きマスの個数を求めてください。 $ T $ 個のテストケースについて答えてください。

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

各テストケースについて、答えを出力せよ。

### Sample Explanation 1 $ 2 $ 個目のテストケースについて、Alice がはじめに $ (1,1) $ に Super King を置いた場合のゲームの進行例を示します。 1. Bob が $ (1,2) $ に石を置く。 2. Alice が Super King を $ (1,1) $ から $ (3,2) $ に移動する。 3. Bob が $ (2,2) $ に石を置く。 4. Alice が Super King を $ (3,2) $ から $ (3,4) $ に移動する。 5. Bob が $ (1,1) $ に石を置く。 6. Alice が Super King を $ (3,4) $ から $ (3,5) $ に移動する。 7. Bob が $ (3,2) $ に石を置く。 8. Alice が $ (3,4) $ に石を置く。 最後の操作の後、Bob は操作を行うことができないため、Alice が勝利します。 このテストケースでは、Alice が勝利できる初期位置は $ 5 $ マスあります。よって答えは $ 5 $ です。 $ 3 $ 個目のテストケースでは、Alice が Super King の初期位置として選ぶことで、Alice が勝利できる空きマスは、 $ 400 $ マスあります。 ### Constraints - $ 1 \le T\le 10^5 $ - $ 2 \le H,W \le 2000 $ - $ 1 \le K \le \max(H, W) -1 $ - $ S_i $ は `.` と `#` からなる長さ $ W $ の文字列 - `.` であるマスが少なくとも $ 1 $ つ存在する - すべてのテストケースについての $ H \times W $ の総和は $ 4\times 10^6 $ 以下 - 入力される数値はすべて整数