题目描述

给你一个 $H\times W$ 的网格 $S$，仅由 # 和 . 组成。

求其中有多少个矩形区域，其中 # 和 . 的个数相等。

形式化地，求满足以下条件的整数四元组 $(u,d,l,r)$ 的个数：

• $1\le u\le d\le H$
• $1\le l\le r\le W$
• $\sum\limits_{i=u}^d\sum\limits_{j=l}^r[S_{i,j}=$#$]=\sum\limits_{i=u}^d\sum\limits_{j=l}^r[S_{i,j}=$.$]$

输入格式

多组数据。第一行一个整数 $T(1\le T\le 2.5\times 10^4)$，表示数据组数。

对于每组数据：
第一行两个整数 $H,W$。
接下来 $H$ 行，每行一个长为 $W$ 的，由 # 和 . 组成的字符串 $S_i$。

保证单个测试点中，$\sum (HW)\le 3\times 10^5$。

输出格式

对于每组数据，输出一行一个整数表示答案。

输入输出样例 #1

输入 #1

3
3 2
##
#.
..
6 6
..#...
..#..#
#.#.#.
.###..
######
.###..
15 50
.......................#...........###.###.###.###
....................#..#..#..........#.#.#...#.#..
.................#...#####...#.....###.#.#.###.###
..................#..##.##..#......#...#.#.#.....#
...................#########.......###.###.###.###
....................#.....#.......................
.###........##......#.....#..#...#.####.####.##..#
#..#.........#......#.....#..#...#.#....#....##..#
#..#.........#......#.....#..#...#.#....#....##..#
#.....##...###..##..#.....#..#...#.#....#....#.#.#
#....#..#.#..#.#..#.#..##.#..#...#.####.####.#.#.#
#....#..#.#..#.####.#....##..#...#.#....#....#.#.#
#....#..#.#..#.#....#.....#..#...#.#....#....#..##
#..#.#..#.#..#.#..#.#....#.#.#...#.#....#....#..##
.##...##...####.##...####..#..###..####.####.#..##

输出 #1

4
79
4032

说明/提示

样例解释

样例包含三组测试数据。

对于第一组数据，满足条件的 $4$ 个四元组如下：

• $(1,2,2,2)$
• $(2,3,1,1)$
• $(2,2,1,2)$
• $(1,3,1,2)$