Felix 为他的生日派对点了一份巨大的矩形比萨。他只是快速去了一趟厨房拿盘子和餐具，当他回来时，宾客们已经开始自便，吃掉了比萨的各个部分。这份比萨原本由 $h \times w$ 个大小相同的正方形小块组成，现在已经缺失了其中的一些小块：

图 F.1：第一个样例的图示，将其划分为边长为 2 的正方形。

为了确保剩余比萨的分配能够更加有序地进行，Felix 想要将剩余的比萨划分为更大的正方形区域。Felix 只能沿着网格线进行切割，并且不能重新排列比萨的任何部分。每个正方形都应该具有相同的边长，且该边长应尽可能大，以减少所需的盘子数量。

求出这个最大可能的边长。注意，答案总是存在的，因为比萨总是可以被划分为 $1 \times 1$ 的正方形。

输入格式

输入包含：

• 第一行包含两个整数 $h$ 和 $w$（$1 \le h, w \le 2500$），表示网格的高度和宽度。
• 接下来的 $h$ 行，每行包含一个长度为 $w$ 的字符串，由 '#'（表示仍然存在的比萨块）和 '.'（表示已经被拿走的比萨块）组成。

输入保证至少包含一个 '#'。

输出格式

输出一个整数，表示最大可能的边长，使得剩余的比萨可以被划分为该边长的正方形。

样例

样例输入 1

4 7
####...
####.##
.######
.####..

样例输出 1

2

样例输入 2

3 5
#####
#####
###..

样例输出 2

1

样例输入 3

3 5
.##..
#####
##.##

样例输出 3

1

样例输入 4

5 13
....###......
....###..###.
.######..###.
.###.....###.
.###.........

样例输出 4

3