#include <bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;

constexpr int INF = (1 << 12);
constexpr int dir[5] = {0, 1, 0, -1, 0};

bool ispower(int n)
{
    return n == (pow(2, static_cast<int>(log2(n))));
}

void bfs_dist(const vector<vector<int>>& room, const pii& pos, vector<int>& dist, const vector<pii>& dirty)
{
    const int h = room.size();
    const int w = room[0].size();
    int rest = dirty.size();
    vector<vector<bool>> checked(h, vector<bool>(w, false));
    vector<bool> visited(dirty.size(), false);
    queue<pair<pii, int>> q;
    q.push(make_pair(pos, 0));
    checked[pos.first][pos.second] = true;
    while (not q.empty()) {
        const pii p = q.front().first;
        const int distance = q.front().second;
        const int pi = p.first;
        const int pj = p.second;
        for (int i = 0; i < dirty.size(); i++) {
            if (p == dirty[i] and (not visited[i])) {
                dist[i] = distance;
                visited[i] = true;
                rest--;
                if (rest == 0) {
                    return;
                }
            }
        }
        q.pop();
        for (int d = 0; d < 4; d++) {
            const int newi = pi + dir[d];
            const int newj = pj + dir[d + 1];
            if (0 <= newi and newi < h and 0 <= newj and newj < w) {
                if (room[newi][newj] != -1 and (not checked[newi][newj])) {
                    checked[newi][newj] = true;
                    q.push(make_pair(make_pair(newi, newj), distance + 1));
                }
            }
        }
    }
}

int main()
{
    while (true) {
        int h, w;
        cin >> w >> h;
        if (w == 0 and h == 0) {
            break;
        }
        vector<vector<int>> room(h, vector<int>(w));

        pii start;
        vector<pii> dirty;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                char c;
                cin >> c;
                if (c == '.') {
                    room[i][j] = 0;
                } else if (c == '*') {
                    room[i][j] = 1;
                    dirty.push_back(make_pair(i, j));
                } else if (c == 'x') {
                    room[i][j] = -1;
                } else {
                    room[i][j] = 0;
                    start.first = i;
                    start.second = j;
                }
            }
        }

        const int dirtynum = dirty.size();
        vector<vector<int>> dist(dirtynum, vector<int>(dirtynum, INF));
        vector<int> initdist(dirtynum, INF);
        bfs_dist(room, start, initdist, dirty);
        for (int i = 0; i < dirtynum; i++) {
            bfs_dist(room, dirty[i], dist[i], dirty);
        }

        bool flag = false;
        for (int i = 0; i < dirtynum; i++) {
            if (initdist[i] == INF) {
                cout << -1 << endl;
                flag = true;
                break;
            }
        }
        if (flag) {
            continue;
        }

        const int maximum = 1 << dirtynum;
        vector<vector<int>> dp(maximum, vector<int>(dirtynum, INF));  // dp[visited[last]
        for (int n = 1; n < maximum; n++) {
            for (int i = 0; i < dirtynum; i++) {
                if ((n >> i) % 2) {
                    for (int j = 0; j < dirtynum; j++) {  //i->j
                        if ((n >> j) % 2) {
                            if (i == j) {
                                if (ispower(n)) {
                                    dp[n][i] = initdist[i];
                                }
                                continue;
                            }
                            dp[n][j] = min(dp[n][j], dp[n - (1 << j)][i] + dist[i][j]);
                        }
                    }
                }
            }
        }
        int mini = INF;
        for (int i = 0; i < dirtynum; i++) {
            mini = min(mini, dp[maximum - 1][i]);
        }
        cout << mini << endl;
    }
    return 0;
}

Measured memory_bytes: 3344