#include <bits/stdc++.h>

//{{{ graph.hpp
#ifndef INCLUDE_GRAPH_HPP
#define INCLUDE_GRAPH_HPP
#include <vector>
namespace orislib {
struct Edge {
  typedef int weight_t;
  int from, to;
  weight_t w;
  Edge(int from, int to, weight_t w) : from(from), to(to), w(w) {}
  bool operator<(const Edge& e) const {
    return w != e.w ? w > e.w : from != e.from ? from < e.from : to < e.to;
  }
  static const weight_t INF;
};
const int Edge::INF=INT_MAX;
typedef std::vector<Edge> Edges;
typedef std::vector<Edges> Graph;
}
#endif
//}}}

using namespace std;
using namespace orislib;

typedef long long ll;
typedef long double ld;
typedef tuple<int, int> duo;
const int dx[] = {0, 0, 1, -1, 1, 1, -1, -1};
const int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};
const int Mod = 1000000000 + 0;
//{{{ templates
#define TT_ template<typename T>inline
#define TTF_ template<typename T,typename F>inline
TT_ T sq(T x){return x*x;}
TT_ T In(){T x;cin>>x;return x;}
TT_ void Out(T&x){cout<<x;}
TT_ void sort(T&v){sort(begin(v),end(v));}
TT_ void revs(T&v){reverse(begin(v),end(v));}
TT_ void uniq(T&v){sort(v);v.erase(unique(begin(v),end(v)),end(v));}
TT_ int ubnd(T&v,typename T::value_type x){return upper_bound(begin(v),end(v),x)-begin(v);}
TT_ int lbnd(T&v,typename T::value_type x){return lower_bound(begin(v),end(v),x)-begin(v);}
TTF_ void inpt(T&v,int n,F f){for(v.reserve(n);n--;v.emplace_back(f()));}
TTF_ void show(T&v,F f,string d=" ",string e="\n"){int i=0;for(auto&x:v)i++&&(cout<<d),f(x);cout<<e;}
TT_ typename T::iterator minel(T&v){return min_element(begin(v),end(v));}
TT_ typename T::iterator maxel(T&v){return max_element(begin(v),end(v));}

inline void fast_io(){ios_base::sync_with_stdio(0);cin.tie(0);}
inline int in(){int x;scanf("%d",&x);return x;}
inline ll pow_mod(ll a,ll k,ll m){ll r=1;for(;k>0;a=a*a%m,k>>=1)if(k&1)r=r*a%m;return r;}
inline ll mod_inv(ll a,ll p){return pow_mod(a,p-2,p);}
//}}} priority_queue queue deque front stringstream max_element min_element insert count make_tuple

//{{{ void dijkstra(g, s, &dist, &prev)
void dijkstra(const Graph& g, int s, vector<Edge::weight_t>& dist, vector<int>& prev)
{
  const int V = g.size();
  prev.assign(V, -1);
  dist.assign(V, Edge::INF);
  dist[s] = 0;
  priority_queue<Edge> pq;
  for (pq.push(Edge(-2, s, 0)); !pq.empty();){
    Edge c = pq.top();
    pq.pop();
    if (prev[c.to] != -1) continue;
    prev[c.to] = c.from;
    for (const auto& e : g[c.to]){
      if (dist[e.to] > e.w + c.w){
        dist[e.to] = e.w + c.w;
        pq.push(Edge(e.from, e.to, e.w + c.w));
      }
    }
  }
}
//}}}

int main()
{
  int w, h;
  while (w = in(), h = in()){
    Graph g(w * h);
    char field[128][128];
    for (int i = 0; i < h; i++) scanf("%s", field[i]);
    int s;
    for (int i = 0; i < h; i++){
      for (int j = 0; j < w; j++){
        if (field[i][j] == '&'){
          s = i * w + j;
          field[i][j] = '.';
        }
        for (int d = 0; d < 4; d++){
          int nx = j + dx[d], ny = i + dy[d];
          if (nx < 0 || w <= nx || ny < 0 || h <= ny) continue;
          g[i * w + j].emplace_back(i * w + j, ny * w + nx, field[i][j] == '.' && field[ny][nx] == '#');
        }
      }
    }
    vector<int> dist, prev;
    dijkstra(g, s, dist, prev);
    int mini = 1000000;
    for (int i = 0; i < h; i++){
      mini = min(mini, dist[i * w]);
      mini = min(mini, dist[i * w + w - 1]);
    }
    for (int i = 0; i < w; i++){
      mini = min(mini, dist[i]);
      mini = min(mini, dist[(h - 1) * w + i]);
    }
    printf("%d\n", mini);
  }

  return 0;
}
### Prompt

Develop a solution in cpp to the problem described below:

Now, a ninja is planning to sneak into the castle tower from outside the castle. This ninja can easily run on the ground and swim in the moat, but he is not very good at climbing up from the moat, so he wants to enter the moat as few times as possible.

Create a program that takes a sketch of the castle as input and outputs the minimum number of times you have to crawl up from the moat from outside the castle to the castle tower. The sketch of the castle is given as a two-dimensional grid. The symbols drawn on the sketch show the positions of "&" indicating the position of the castle tower and "#" indicating the position of the moat, and "." (Half-width period) at other points. In addition, it is assumed that there is only one castle tower in the castle, and the ninja moves one square at a time in the north, south, east, and west directions when running or swimming, and does not move diagonally.



Input

A sequence of multiple datasets is given as input. The end of the input is indicated by two lines of zeros. Each dataset is given in the following format:


n m
c1,1 c1,2 ... c1, n
c2,1c2,2 ... c2, n
::
cm, 1cm, 2 ... cm, n


The first line gives the east-west width n and the north-south width m (1 ≤ n, m ≤ 100) of the sketch. The following m lines give the information on the i-th line of the sketch. Each piece of information is a character string of length n consisting of the symbols "&", "#", and ".".

The number of datasets does not exceed 50.

Output

Outputs the minimum number of times (integer) that must be climbed from the moat for each dataset on one line.

Examples

Input

5 5
.###.
#...#
#.&.#
#...#
.###.
18 15
..####....####....
####..####....####
#...............##
.#.############.##
#..#..........#.##
.#.#.########.#.##
#..#.#......#.#.##
.#.#....&...#.#.##
#..#........#.#.##
.#.#.########.#.##
#..#..........#.##
.#.############.##
#...............##
.#################
##################
9 10
#########
........#
#######.#
#.....#.#
#.###.#.#
#.#&#.#.#
#.#...#.#
#.#####.#
#.......#
#########
9 3
###...###
#.#.&.#.#
###...###
0 0


Output

1
2
0
0


Input

5 5
.###.
...#
.&.#
...#
.###.
18 15
..####....####....
..####....####
...............##
.#.############.##
..#..........#.##
.#.#.########.#.##
..#.#......#.#.##
.#.#....&...#.#.##
..#........#.#.##
.#.#.########.#.##
..#..........#.##
.#.############.##
...............##
.#################

9 10

........#
.#
.....#.#
.###.#.#
.#&#.#.#
.#...#.#
.#####.#
.......#

9 3
...###
.#.&.#.#
...###
0 0
</pre>


Output

1
2
0
0

### Response

```cpp
#include <bits/stdc++.h>

//{{{ graph.hpp
#ifndef INCLUDE_GRAPH_HPP
#define INCLUDE_GRAPH_HPP
#include <vector>
namespace orislib {
struct Edge {
  typedef int weight_t;
  int from, to;
  weight_t w;
  Edge(int from, int to, weight_t w) : from(from), to(to), w(w) {}
  bool operator<(const Edge& e) const {
    return w != e.w ? w > e.w : from != e.from ? from < e.from : to < e.to;
  }
  static const weight_t INF;
};
const int Edge::INF=INT_MAX;
typedef std::vector<Edge> Edges;
typedef std::vector<Edges> Graph;
}
#endif
//}}}

using namespace std;
using namespace orislib;

typedef long long ll;
typedef long double ld;
typedef tuple<int, int> duo;
const int dx[] = {0, 0, 1, -1, 1, 1, -1, -1};
const int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};
const int Mod = 1000000000 + 0;
//{{{ templates
#define TT_ template<typename T>inline
#define TTF_ template<typename T,typename F>inline
TT_ T sq(T x){return x*x;}
TT_ T In(){T x;cin>>x;return x;}
TT_ void Out(T&x){cout<<x;}
TT_ void sort(T&v){sort(begin(v),end(v));}
TT_ void revs(T&v){reverse(begin(v),end(v));}
TT_ void uniq(T&v){sort(v);v.erase(unique(begin(v),end(v)),end(v));}
TT_ int ubnd(T&v,typename T::value_type x){return upper_bound(begin(v),end(v),x)-begin(v);}
TT_ int lbnd(T&v,typename T::value_type x){return lower_bound(begin(v),end(v),x)-begin(v);}
TTF_ void inpt(T&v,int n,F f){for(v.reserve(n);n--;v.emplace_back(f()));}
TTF_ void show(T&v,F f,string d=" ",string e="\n"){int i=0;for(auto&x:v)i++&&(cout<<d),f(x);cout<<e;}
TT_ typename T::iterator minel(T&v){return min_element(begin(v),end(v));}
TT_ typename T::iterator maxel(T&v){return max_element(begin(v),end(v));}

inline void fast_io(){ios_base::sync_with_stdio(0);cin.tie(0);}
inline int in(){int x;scanf("%d",&x);return x;}
inline ll pow_mod(ll a,ll k,ll m){ll r=1;for(;k>0;a=a*a%m,k>>=1)if(k&1)r=r*a%m;return r;}
inline ll mod_inv(ll a,ll p){return pow_mod(a,p-2,p);}
//}}} priority_queue queue deque front stringstream max_element min_element insert count make_tuple

//{{{ void dijkstra(g, s, &dist, &prev)
void dijkstra(const Graph& g, int s, vector<Edge::weight_t>& dist, vector<int>& prev)
{
  const int V = g.size();
  prev.assign(V, -1);
  dist.assign(V, Edge::INF);
  dist[s] = 0;
  priority_queue<Edge> pq;
  for (pq.push(Edge(-2, s, 0)); !pq.empty();){
    Edge c = pq.top();
    pq.pop();
    if (prev[c.to] != -1) continue;
    prev[c.to] = c.from;
    for (const auto& e : g[c.to]){
      if (dist[e.to] > e.w + c.w){
        dist[e.to] = e.w + c.w;
        pq.push(Edge(e.from, e.to, e.w + c.w));
      }
    }
  }
}
//}}}

int main()
{
  int w, h;
  while (w = in(), h = in()){
    Graph g(w * h);
    char field[128][128];
    for (int i = 0; i < h; i++) scanf("%s", field[i]);
    int s;
    for (int i = 0; i < h; i++){
      for (int j = 0; j < w; j++){
        if (field[i][j] == '&'){
          s = i * w + j;
          field[i][j] = '.';
        }
        for (int d = 0; d < 4; d++){
          int nx = j + dx[d], ny = i + dy[d];
          if (nx < 0 || w <= nx || ny < 0 || h <= ny) continue;
          g[i * w + j].emplace_back(i * w + j, ny * w + nx, field[i][j] == '.' && field[ny][nx] == '#');
        }
      }
    }
    vector<int> dist, prev;
    dijkstra(g, s, dist, prev);
    int mini = 1000000;
    for (int i = 0; i < h; i++){
      mini = min(mini, dist[i * w]);
      mini = min(mini, dist[i * w + w - 1]);
    }
    for (int i = 0; i < w; i++){
      mini = min(mini, dist[i]);
      mini = min(mini, dist[(h - 1) * w + i]);
    }
    printf("%d\n", mini);
  }

  return 0;
}
```