Bajtazar 正在为拜托茨（Bajtocja）市中心规划一座新机场。机场占地为一个 $n \times n$ 的正方形，在规划图上被划分为 $n^2$ 个 $1 \times 1$ 的方格。其中一些方格已经被预定的建筑物（出发和到达大厅、控制塔、机库）占用。Bajtazar 的任务是规划 $m$ ($m \le 2$) 条长度相同的跑道。

每条长度为 $k$ 的跑道必须由 $k$ 个相邻的空闲方格组成，形成一个 $1 \times k$ 或 $k \times 1$ 的矩形。跑道必须互不重叠（在 $m=2$ 的情况下），且不能包含任何被占用的方格。Bajtazar 想知道，在机场内能够容纳的跑道的最大长度是多少。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 1500, 1 \le m \le 2$)，分别表示机场的边长和需要建造的跑道数量。

接下来的 $n$ 行描述了机场的布局；每行包含一个长度为 $n$ 的字符串，由字符 X（被占用的方格）或 .（空闲方格）组成。

输出格式

输出一行，包含一个整数 $k$，表示可以规划的跑道的最大长度。

样例

样例输入 1

5 2
.X...
.XXXX
XX...
.....
.X.X.

样例输出 1

3

说明 1

下图展示了长度为 3 的跑道的一种可能布局：

.X...
.XXXX
XX..2
111.2
.X.X2

子任务

测试集分为以下子任务。每个子任务的测试用例由一组或多组独立的测试数据组成。