AT_abc410_f [ABC410F] Balanced Rectangles

$ H \times W $ のグリッドが与えられ、各マスには `#` か `.` のどちらかが書かれています。 各マスに書かれている記号の情報は $ H $ 個の長さ $ W $ の文字列 $ S_1,S_2,\dots,S_H $ として与えられ、上から $ i $ 行目、左から $ j $ 列目にあるマスには $ S_i $ の $ j $ 文字目と同じ記号が書かれています。 このグリッドに対し、以下の条件を全て満たす長方領域がいくつあるか求めてください。 - 長方領域に含まれる `#` が書かれたマスの個数と `.` が書かれたマスの個数が等しい。 厳密には、次の条件を全て満たす $ 4 $ つの整数の組 $ (u,d,l,r) $ の数を求めてください。 - $ 1 \le u \le d \le H $ - $ 1 \le l \le r \le W $ - グリッドのうち上から $ u $ 行目から $ d $ 行目、左から $ l $ 列目から $ r $ 列目の部分を取り出す。このとき、取り出した部分に含まれる `#` が書かれたマスの個数と `.` が書かれたマスの個数が等しい。 $ 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 $ 行目 には $ i $ 番目のテストケースに対する答えを出力せよ。

### Sample Explanation 1 この入力には $ 3 $ 個のテストケースが含まれます。 $ 1 $ 番目のケースについて、以下の $ 4 $ 個の長方領域が問題文中の条件を満たします。 - 上から $ 1 $ 行目から $ 2 $ 行目、左から $ 2 $ 列目から $ 2 $ 列目 - 上から $ 2 $ 行目から $ 3 $ 行目、左から $ 1 $ 列目から $ 1 $ 列目 - 上から $ 2 $ 行目から $ 2 $ 行目、左から $ 1 $ 列目から $ 2 $ 列目 - 上から $ 1 $ 行目から $ 3 $ 行目、左から $ 1 $ 列目から $ 2 $ 列目 ### Constraints - $ 1 \le T \le 25000 $ - $ 1 \le H,W $ - ひとつの入力に含まれる $ H \times W $ の総和は $ 3 \times 10^5 $ を超えない。 - $ S_i $ は `#` と `.` からなる長さ $ W $ の文字列である。