Construction Complete!
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

指挥官想要在战场上建造一座新的生产建筑.

整个战场可以视为一个n行m列的二维网格,有一些网格中已经建造了一些生产建筑,还有一些网格是矿区,斜坡,悬崖等无法建造建筑的地方,剩下的位置是可以建造建筑的空地.

现在指挥官想建造一座新的占据r行c列网格的矩形建筑,但是必须要满足以下要求.
  1. 建筑占据的所有网格都必须为空地.
  2. 新的建筑必须在已有的建筑基础上延伸建造,即新建筑与距离其最近的已有建筑之间距离不能超过d.
把第x行,第y列的网格的表示为(x, y),则(x_1, y_1)与(x_2, y_2)之间的距离为|x_1 - x_2| + |y_1 - y_2|.

新矩形建筑与(x, y)之间的距离为矩形建筑占据的所有网格与(x, y)之间的距离中的最小值.

你是指挥官的顾问,现在指挥官想让你帮忙计算建造一座占据r行c列网格的矩形新建筑的方案数量.

对于两种方案,如果矩形新建筑最左上角的网格位置是不同的,则我们认为这两种建造方案是不同的.

输入描述:

本题含有多组测试数据,

第1行包含一行一个正整数T(1 \leq T \leq 10^5),表示测试数据的数目,然后输入T组独立的数据.

每组数据第1行输入一行五个以空格分隔的正整数n, m, r, c, d,分别表示战场的行数和列数,新建筑占据的行数和列数,以及已有建筑能延伸的最大距离.

数据范围满足2 \leq n \cdot m \leq 10^6, 1 \leq r \leq n, 1 \leq c \leq m, 1 \leq d \leq n + m - 2.

接下来输入n行,每行m个字符表示战场的情况.第i行的第j个字符代表坐标为(i, j)的方格情况,如果字符是'x',则表示该位置是已有的生产建筑,如果字符是'#'则表示该位置是矿区,斜坡,悬崖等无法建造建筑的地方,如果字符是'.',则表示该位置是空地.

保证所有测试数据的n \cdot m之和不超过10^6.

输出描述:

对于每组测试数据输出一行一个非负整数表示建造方案的数量.
示例1

输入

复制 
1
3 3 2 2 1
x..
#..
...

输出

复制 
1

说明

对于样例,仅有1种合法的建造方案,即让新矩形建筑的左上角位于第1行第2列的网格.

矩形建筑左上角位于第1行第2列的网格时,矩形一共包含4个网格,分别为(1, 2), (1, 3), (2, 2), (2, 3),这4个网格都是空地,并且空地(1, 2)距离已有建筑(1, 1)的距离为1,因此满足建造新建筑的条件.

如果矩形建筑左上角位于第2行第2列的网格,虽然矩形包含的4个网格也都是空地,但是这4个网格距离唯一的已有建筑(1,1)的距离都超过1,因此不是一种合法的建造方案.