直方图是一个简单的直角多边形 $H$（即每个顶点的内角均为 $90^\circ$ 或 $270^\circ$），且其有一条水平边能“看到” $H$ 内部（即内部或边界上）的每一个点 $q$。在此，如果存在一条位于 $H$ 内部且连接边 $e$ 与点 $q$ 的垂直线段 $s$，则称边 $e$ 能看到点 $q \in H$。

令 $H$ 为一个具有 $n$ 个顶点的直方图，考虑将 $H$ 分解为若干个边平行于坐标轴的矩形 $R$。矩形的顶点不一定必须是 $H$ 的顶点：允许在 $H$ 的边界上和/或其内部引入额外的顶点。对于这样的分解 $R$，一条位于 $H$ 内部的水平或垂直线段 $s$ 的“刺穿数”（stabbing number）是指其内部（不仅仅是边界）被 $s$ 穿过的来自 $R$ 的矩形数量。分解 $R$ 的刺穿数定义为所有位于 $H$ 内部的水平或垂直线段 $s$ 中，刺穿数的最大值。目标是计算出一个刺穿数最小的分解 $R$。

输入格式

输入的第一行包含两个正整数 $m$ 和 $n$ ($1 \leqslant m, n \leqslant 50$)，分别表示描述直方图的表格的行数和列数。接下来的 $m$ 行，每行包含恰好 $n$ 个字符。“”表示直方图的边界，其余部分用点（“.”）填充。直方图的每条边至少包含三个“”。你可以假设给定的直方图至少有 4 条边，最多有 16 条边，且边不会重叠、相交或接触；即每个“”恰好与另外两个“”字符相邻。

输出格式

输出给定直方图的最小刺穿数。

样例

输入 1

10 13
.....****....
.....*..*....
.....*..***..
.....*....*..
.....*....***
...***......*
...*........*
****........*
*...........*
*************

输出 1

2

输入 2

8 15
...............
.........*****.
....***..*...*.
....*.*..*...*.
.****.****...*.
.*...........*.
.*************.
...............

输出 2

2