Vasya最近开始学习英语。现在他需要记住如何写英文字母。他对其中一些不太确定,所以他决定稍微训练一下。
他找到一张方格纸,开始在那里写下任意英文字母。最后 Vasya 写了 n 行,每行包含 m 个字符。这样,他得到了一个n×m的矩形表格,表格的每个单元格中都包含一些英文字母。让我们用 1 到 n 的整数从上到下对表行进行编号,用 1 到 m 的整数从左到右对表的列进行编号。
之后,Vasya 看着生成的矩形表,想知道有多少个子表符合以下两个条件:
- 子表最多包含 k 个带有“a”字母的单元格;
- 位于子表所有四个角单元格中的所有字母都是相等的。
正式地,子表的定义如下。它由四个整数 x1、y1、x2、y2 定义,其中 1 ≤ x1 < x2 ≤ n、1 ≤ y1 < y2 ≤ m。那么子表包含所有这样的单元格(x,y)(x是行号,y是列号),其中以下不等式成立x1≤x≤x2,y1≤y≤y2。表格的角单元格是单元格 (x1, y1)、(x1, y2)、(x2, y1)、(x2, y2)。
Vasya 在一张纸上写信后已经太累了。这就是为什么他要求你数一下他感兴趣的值。
输入
第一行包含三个整数 n、m、k (2 ≤ n, m ≤ 400; 0 ≤ k ≤ n·m)。
接下来的 n 行每行包含 m 个字符 — 给定的表。表中的每个字符都是一个小写英文字母。
输出
打印单个整数 — 所需子表的数量。
示例
输入 #1
3 4 4 aabb baab baab
输出 #1
2
输入 #2
4 5 1 ababa ccaca ccacb cbabc
输出 #2
1
注意
第一个示例中有两个合适的子表:第一个子表的左上角是单元格 (2, 2),右下角是单元格 (3, 3),第二个子表的左上角是单元格 (2, 1),右下角是单元格 (3, 4)。