// 深さ優先探索
#include <bits/stdc++.h>
using namespace std;
#define int long long
using P = pair<int, int>;
constexpr array<int, 8> dx = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr array<int, 8> dy = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr int INF = 1010101010;
constexpr int MOD = 1000000000 + 7;
// constexpr int MOD = 998244353;
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
constexpr int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
constexpr int fact(int n) { return n > 1 ? n * fact(n - 1) % MOD : 1; }
int modinv(int a)
{
    int b = MOD, u = 1, v = 0;
    while (b)
    {
        int t = a / b;
        a -= t * b;
        swap(a, b);
        u -= t * v;
        swap(u, v);
    }
    u %= MOD;
    if (u < 0)
        u += MOD;
    return u;
}
constexpr int modpow(int a, int n)
{
    int rtn = 1;
    while (n > 0)
    {
        if (n & 1)
            rtn = rtn * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return rtn;
}

constexpr char START = '1', GOAL = 'g', PASS = '1', WALL = '0';
// 升目マップを探索する
class squareMap
{
private:
    vector<string> _map;
    int _h, _w;
    pair<int, int> _start{INF, INF}, _goal{INF, INF};
    const bool inMap(pair<int, int> p)
    {
        return 0 <= p.first && p.first < _h && 0 <= p.second && p.second < _w;
    }

public:
    // コンストラクタ 引数mapはマスの種類を文字で表した文字列ベクトルを
    squareMap(vector<string> map);
    ~squareMap();
    bool setStartGoal();
    void setSquare(int y, int x, char square = PASS)
    {
        _map[y][x] = square;
    }
    const char getSquare(int y, int x, char square = PASS)
    {
        return _map[y][x];
    }
    const bool depthFirstSearch();
    // キュー使用幅優先探索で，スタートからゴールにたどり着けるかどうか探索する．
    const bool breadthFirstSearch();
    // キュー使用幅優先探索で，スタートからゴールにたどり着けるかどうか探索する．第一引数には二次元ベクトルを入れて，距離を返す
    const bool breadthFirstSearch(vector<vector<int>> &return_dist);
    const bool goEntire();
    int howMany();
};

squareMap::squareMap(vector<string> map) : _map(map)
{
    _h = _map.size();
    _w = _map.size() > 0 ? _map[0].size() : 0;
    setStartGoal();
}

squareMap::~squareMap()
{
}

bool squareMap::setStartGoal()
{
    // STARTとGOALを探す
    bool start_found = false, goal_found = false;
    for (int i = 0; i < _h; i++)
    {
        string::size_type pos;
        if (!start_found)
        {
            if (string::npos != (pos = _map[i].find(START)))
            {
                start_found = true;
                _start = {i, pos};
            }
        }
        if (!goal_found)
        {
            if (string::npos != (pos = _map[i].find(GOAL)))
            {
                goal_found = true;
                _goal = {i, pos};
            }
        }
        if (start_found && goal_found)
            break;
    }
    return start_found || goal_found;
}

// スタック使用深さ優先探索で，スタートからゴールにたどり着けるかどうか探索する
const bool squareMap::depthFirstSearch()
{
    // 調べる升を記録するスタック
    stack<pair<int, int>> destination;
    // スタートから各升の距離を記録 その升をすでに探索したかどうかも記録 INFは調べていないことを意味する
    vector<vector<int>> distance(_h, vector<int>(_w, INF));

    // 最初にスタートを探索した
    destination.push(_start);
    distance[_start.first][_start.second] = 0;
    _map[_start.first][_start.second] = WALL;

    // 全ての升を調べ終わるか，ゴールが見つかるまで調べる
    while (!destination.empty())
    {
        // スタックから調べる升を取り出す
        pair<int, int> p = destination.top();
        destination.pop();
        // 調べる升がゴールなら終わり
        if (p == _goal)
            break;

        // 次に調べる升の上下左右を調べる
        for (int i = 0; i < dx.size(); i++)
        {
            // np: 次に調べる升の上下左右の升
            pair<int, int> np = {p.first + dy[i], p.second + dx[i]};
            // npが枡目内に存在する，npが壁ではないかつnpをすでに探索していないか確認
            if (0 <= np.first && np.first < _h && 0 <= np.second && np.second < _w && _map[np.first][np.second] != WALL && distance[np.first][np.second] == INF)
            {
                // npを今後調べる升としてスタックに積む
                destination.push(np);
                // npまでの距離を記録する
                distance[np.first][np.second] = distance[p.first][p.second] + 1;
                // 陸を海に変える
                _map[np.first][np.second] = WALL;
            }
        }
    }
    // ゴールまでの距離がINFではない．つまりゴールへたどり着けるかどうかを返す
    return (inMap(_goal)) ? distance[_goal.first][_goal.second] != INF : false;
}

const bool squareMap::breadthFirstSearch()
{
    vector<vector<int>> tmp;
    return breadthFirstSearch(tmp);
}
const bool squareMap::breadthFirstSearch(vector<vector<int>> &return_dist)
{
    // 調べる升を記録するキュー
    queue<pair<int, int>> destination;
    // スタートから各升の距離を記録 その升をすでに探索したかどうかも記録 INFは調べていないことを意味する
    vector<vector<int>> distance(_h, vector<int>(_w, INF));

    // 最初にスタートを探索した
    destination.push(_start);
    distance[_start.first][_start.second] = 0;

    // 全ての升を調べ終わるか，ゴールが見つかるまで調べる
    while (!destination.empty())
    {
        // キューから調べる升を取り出す
        pair<int, int> p = destination.front();
        destination.pop();
        // 調べる升がゴールなら終わり
        if (p == _goal)
            break;

        // 次に調べる升の上下左右を調べる
        for (int i = 0; i < dx.size(); i++)
        {
            // np: 次に調べる升の上下左右の升
            pair<int, int> np = {p.first + dy[i], p.second + dx[i]};
            // npが枡目内に存在する，npが壁ではないかつnpをすでに探索していないか確認
            if (0 <= np.first && np.first < _h && 0 <= np.second && np.second < _w && _map[np.first][np.second] != WALL && distance[np.first][np.second] == INF)
            {
                // npを今後調べる升としてスタックに積む
                destination.push(np);
                // npまでの距離を記録する
                distance[np.first][np.second] = distance[p.first][p.second] + 1;
            }
        }
    }
    // ゴールまでの距離がINFではない．つまりゴールへたどり着けるかどうかを返す
    return_dist = distance;
    return (0 <= _goal.first && _goal.first < _h && 0 <= _goal.second && _goal.second < _w) ? distance[_goal.first][_goal.second] != INF : false;
}

// 全ての道に行くことができるか
const bool squareMap::goEntire()
{
    // 各マスへの距離を得る
    vector<vector<int>> distance;
    breadthFirstSearch(distance);

    // 到達できない道があるか調べる．もしあればすべての道に行くことはできない．
    bool can = true;
    for (int i = 0; i < _h && can; i++)
        for (int j = 0; j < _w && can; j++)
            if (_map[i][j] == PASS && distance[i][j] == INF)
                can = false;
    return can;
}

int squareMap::howMany()
{
    int count = 0;
    while (setStartGoal())
    {
        depthFirstSearch();
        count++;
    }
    return count;
}

signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << setprecision(10);

    // 入力例
    // 5 5
    // ##.##
    // s..##
    // #.###
    // #....
    // #.##g
    int h, w;
    bool is_not_first_ans = false;
    while (cin >> w >> h)
    {
        if(w==0||h==0)
            continue;

        vector<string> map(h);
        for (auto &&row_map : map)
            for (int i = 0; i < w; i++)
            {
                string tmp;
                cin >> tmp;
                row_map.append(tmp);
            }

        squareMap sm(map);

        cout << sm.howMany() << endl;
    }
}



Measured memory_bytes: 3188