题目描述

研究者们想要测试 Misaka Network，于是他们把 Misaka Network 中的所有妹妹们召集到了一起。

现在妹妹们排成了 $N$ 行 $M$ 列，有的位置没有人。现在研究者们给每一个个体的超能力进行了评定，一共有三个能力等级：Level 1 低能力者、Level 2 异能力者 和 Level 3 超能力者。研究者们每次测试可以选取一个子矩形内的所有个体，为了保证高效，他们不希望这个矩形内存在空的位置。并且，为了保证稳定，他们希望这个矩形内所有个体的能力等级的平均值恰好为 $2$。同时，每个个体最多只能参加一次测试，因此，多次测试选取的矩形应当不相交。

研究者们想知道他们最多能进行多少次测试。

输入格式

第一行两个整数$N$、$M$。

接下来 $N$ 行每行 $M$ 个字符，每个字符表示了队列中对应位置的个体。

1 表示 Level 1 低能力者，2 表示 Level 2 异能力者，3 表示 Level 3 超能力者，* 表示一个空的位置。

输出格式

一行一个整数，表示最多能够进行多少次测试。

2 3
31*
*13

2

6 6
23311*
**13**
11*233
13*223
***133
331***

9

2 50
21111121332233123311312211231333122233133212221212
21332123132223111331233121122331133311112121331311

51

数据范围与提示

对于所有数据 $1 \leq N \times M \leq 10^5$，队列中仅包含 1、2、3、* 四种字符。

|子任务编号|分值|$N \times M$|特殊性质| |:------------:|:----:|:------------:|:--------:|:--------:|:--------:| |1|$5$|$\leq 10^5$|队列中不存在 1| |2|$15$|$\leq 1000$|$N=1$| |3|$15$|$\leq 2000$|$N=2$| |4|$35$|$\leq 2000$|队列中不存在 *| |5|$15$|$\leq 2000$|-| |6|$15$|$\leq 10^5$|-|