AT_abc410_f [ABC410F] Balanced Rectangles

You are given an $ H \times W $ grid, where each cell contains `#` or `.`. The information about the symbols written in each cell is given as $ H $ strings $ S_1,S_2,\dots,S_H $ of length $ W $ , where the cell in the $ i $ -th row from the top and $ j $ -th column from the left contains the same symbol as the $ j $ -th character of $ S_i $ . Find the number of rectangular regions in this grid that satisfy all of the following conditions: - The number of cells containing `#` and the number of cells containing `.` in the rectangular region are equal. Formally, find the number of quadruples of integers $ (u,d,l,r) $ that satisfy all of the following conditions: - $ 1 \le u \le d \le H $ - $ 1 \le l \le r \le W $ - When extracting the part of the grid from the $ u $ -th through $ d $ -th rows from the top and from the $ l $ -th through $ r $ -th columns from the left, the number of cells containing `#` and the number of cells containing `.` in the extracted part are equal. You are given $ T $ test cases. Find the answer for 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. The $ i $ -th line should contain the answer for the $ i $ -th test case.

### Sample Explanation 1 This input contains $ 3 $ test cases. For the $ 1 $ st case, the following $ 4 $ rectangular regions satisfy the conditions in the problem statement: - From the $ 1 $ st to $ 2 $ nd rows from the top, from the $ 2 $ nd to $ 2 $ nd columns from the left - From the $ 2 $ nd to $ 3 $ rd rows from the top, from the $ 1 $ st to $ 1 $ st columns from the left - From the $ 2 $ nd to $ 2 $ nd rows from the top, from the $ 1 $ st to $ 2 $ nd columns from the left - From the $ 1 $ st to $ 3 $ rd rows from the top, from the $ 1 $ st to $ 2 $ nd columns from the left ### Constraints - $ 1 \le T \le 25000 $ - $ 1 \le H,W $ - The sum of $ H \times W $ over all test cases in one input does not exceed $ 3 \times 10^5 $ . - $ S_i $ is a string of length $ W $ consisting of `#` and `.`.