問題文


問題名の元ネタ: AtCoder Beginner Contest 176 D - Wizard in Maze

Teto ちゃんの家の庭の木々の間に有刺鉄線が張られています。
この庭の地図を のマス目で表し、左から 列目で、上から 番目のマスを マス と表します。
いくつかのマスの中にはそれぞれ 本の木が生えています。マスの境界には木はありません。
互いに辺で隣り合うマスに生えている 本の木は有刺鉄線でつながれている可能性があり、その 本の木の間を通る経路は危険です。

今、彼女はマス の右下角の点におり、庭の外まで移動しようとしています。
移動する前に、次のような魔法を何度でも使えます。

  • 魔法:上下 マス、左右 マスからなる の範囲を選び、その中に生えている木をすべて消します。
    ただし、範囲の縦横を入れ替えることはできず、範囲の境界はマスの境界と一致しなければなりません。

この魔法によって 本の木が隣り合わなくなった場所は、ワイヤーも取り除かれ、危険ではなくなります。

の値と、各マスに木が生えているかの情報が与えられます。
危険な経路を通らずに庭の外まで移動するとき、魔法を使う回数の最小値を求めてください。
経路の太さはないものとします。

入力


入力は以下の形式で与えられます。





は長さ の文字列です。 文字目を と表します。
は、マス に木が生えているなら # 、生えていなければ . です。
の間には空白はありません。

他に入力は以下の制約を満たします。

  • は整数

出力


魔法を使う回数の最小値を出力してください。
最後に改行してください。

サンプル


入力例1


3 6 6
.#####
#.##.#
##..##
#.#..#
##.###
####..

出力例1


0

マス目の左斜め上に向かって進む経路は危険ではありません。

入力例2


5 2 1
#.########
##########
#.########
##.######.
#########.
#########.
#########.
#..#######
#..#######
##########

出力例2


3

魔法を使う範囲の縦横を入れ替えることはできません。

入力例3


9 18 18
.....#............
.#####.###########
.#...#.#.........#
.#.#.#.#.#######.#
.#.#.#.#.#.....#.#
.#.#.#.#.#.###.#.#
.#.#.#.#.#.#.#.#.#
.#.#.#.#.#.#.#.#.#
.#.#.#.#.#.#.#.#.#
.#.#.#.#.#.#.#.#.#
.#.#.#.#####.#.#.#
.#.#.#.......#.#.#
.#.#.#########.#.#
.#.#...........#.#
.#.#############.#
.#...............#
.#################
..................

出力例3


1

提出


Go (1.14)