#include <stdio.h>
#include <string.h>
#include <queue>
#include <assert.h>
#include <algorithm>
using namespace std;
char g[64][64];
int dist[64][64], walldist[64][64][4];
int n, m;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
struct State {
    int x, y;
    int g, h;
    State(int a=0, int b=0, int c=0, int d=0):
        x(a), y(b), g(c), h(d) {}
    bool operator<(const State &a) const {
        return h > a.h;
    }
};
int dp[40][40][40 * 40];
int search(int sx, int sy, int ex, int ey) {
    priority_queue<State> pQ;
    State u, v;
    int tx, ty, h;
    pQ.push(State(sx, sy, 0, 0));
    memset(dp, 63, sizeof(dp));
    while (!pQ.empty()) {
        u = pQ.top(), pQ.pop();
        if (u.h > dp[u.x][u.y][u.g])
            continue;
        if (u.x == ex && u.y == ey)
            return u.h;
        for (int i = 0; i < 4; i++) {
            tx = u.x + dx[i], ty = u.y + dy[i];
            if (tx < 0 || ty < 0 || tx >= n || ty >= m)
                continue;
            if (g[tx][ty] == '#' || g[tx][ty] == 'E')
                continue;
            if (g[tx][ty] == '.') 
                h = max(u.h, u.g + walldist[u.x][u.y][i]);
            else if (g[tx][ty] == 'X')
                h = max(u.h, u.g);
            assert(u.g + 1 < 40 * 40);
            if (dp[tx][ty][u.g + 1] > h) {
                dp[tx][ty][u.g + 1] = h;
                pQ.push(State(tx, ty, u.g + 1, h));
            }
        }
    }
    return 0;
}
void bfs(int sx, int sy) {
    memset(dist, 63, sizeof(dist));
    queue<int> X, Y;
    int tx, ty;
    X.push(sx), Y.push(sy);
    dist[sx][sy] = 0;
    while (!X.empty()) {
        sx = X.front(), X.pop();
        sy = Y.front(), Y.pop();
        for (int i = 0; i < 4; i++) {
            tx = sx + dx[i], ty = sy + dy[i];
            if (tx < 0 || ty < 0 || tx >= n || ty >= m)
                continue;
            if (g[tx][ty] == '#' || dist[tx][ty] <= dist[sx][sy] + 1)
                continue;
            dist[tx][ty] = dist[sx][sy] + 1;
            X.push(tx), Y.push(ty);
        }
    }
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; i++)
            scanf("%s", g[i]);
        int sx, sy, ex, ey, tx, ty;
        
        memset(walldist, 0, sizeof(walldist));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g[i][j] == 'E')	sx = i, sy = j;
                if (g[i][j] == 'X')	ex = i, ey = j;				
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g[i][j] != '.')
                    continue;
                g[i][j] = '#';
                bfs(ex, ey);
                for (int k = 0; k < 4; k++) {
                    tx = i + dx[k], ty = j + dy[k];
                    if (tx < 0 || ty < 0 || tx >= n || ty >= m)
                        continue;
                    if (g[tx][ty] == '#')
                        continue;
                    walldist[tx][ty][(k+2)%4] = dist[tx][ty];
                }
                g[i][j] = '.';
            }
        }
        int ret = search(sx, sy, ex, ey);
        printf("%d\n", ret);
    }
    return 0;
}
/*
2
8 8
..X.....
........
##.##...
........
##.##...
##.##...
........
..E.....
 
3 4
..X.
.##.
.E..
*/

#include <stdio.h>
#include <map>
#include <vector>
#include <iostream>
#include <fstream>
#include <assert.h>
#include <sstream>
#include <math.h>
#include <ctype.h>
#include <string>
#include <string.h>
#include <set>
#include <algorithm>
using namespace std;
class XMLParser {
    public:
    struct Node {
        string tag_name, content;
        map<string, string> attr;
        vector<Node> child;
    };
    Node root; 
    XMLParser(string text = "") {
        sin << text;
        root = Node();
        build(root, "");
    }	
    void replaceAll(std::string& str, const std::string& from, const std::string& to) {
    	if(from.empty())
        	return;
    	size_t start_pos = 0;
    	while((start_pos = str.find(from, start_pos)) != std::string::npos) {
        	str.replace(start_pos, from.length(), to);
        	start_pos += to.length(); // In case 'to' contains 'from', like replacing 'x' with 'yx'
    	}
    }
    string html2text(string s) {
        string ret(s);
        replaceAll(ret, "&amp;amp;quot;", "\"");
        replaceAll(ret, "&amp;amp;", "and");
        return ret;
    }
    private:
    stringstream sin;
    void getTagContent(Node &u) {
        char c, div;
        while (sin.get(c)) {
            if (c == '<') {
                while (sin.get(c) && isspace(c));
                u.tag_name = c;
                while (sin.get(c) && c != '>' && !isspace(c))
                    u.tag_name += c;
                if (c == '>')	return;
                while (true) {
                    while (sin.get(c) && isspace(c));
                    if (c == '>')	return;
                    string a = "", b = "";
                    a += c;
                    while (sin.get(c) && !isspace(c) && c != '=')
                        a += c;
                    while (sin.get(c) && (isspace(c) || c == '"' || c == '\'')) div = c;
                    b += c;
                    while (sin.get(c) && !isspace(c) && c != div)
                        b += c;
                    u.attr[a] = b;
                }
                return;
            }
        }
    }
    int build(Node &u, string last) {
        getTagContent(u);
        if (u.tag_name == last)
            return 0;
        while (sin.peek() != EOF && sin.peek() != '<') {
            char c;
            sin.get(c);
            u.content += c;
        }
        u.content = html2text(u.content);
        while (sin.peek() != EOF) {
            while (sin.peek() != EOF && isspace(sin.peek()))
                sin.get();
            if (sin.peek() == '<') {
                u.child.push_back(Node());
                if (!build(u.child[u.child.size() - 1], "/" + u.tag_name)) {
                    u.child.pop_back();
                    break;
                }
            }
        }	
        return 1;	
    }
};
class StatsModel {
    public: 
        map<string, map<string, int> > categories; 	// count(w, c)
        map<string, int > commentCount; 			// N_{c}
        map<string, int > count_category; 			// count(c)
        map<string, map<string, int> > judgeTable;
        int N, V;
        int microtable[2][2]; // [truth 0:1][classifier 0:1]
        StatsModel() {
            N = V = 0;
            memset(microtable, 0, sizeof(microtable));
        }
        vector<string> normalSentence(string content) {
            vector<string> w;
            stringstream sin(content);
            string token;
            while (sin >> token) {
                token = igntrim(token);
                token = str2lower(token);
                if (token.length() > 0)
                    w.push_back(token);
            }
            return w;
        }
        void recordJudge(string truth, string classifier) {
            judgeTable[truth][classifier]++;
            for (map<string, int>::iterator it = commentCount.begin();
                it != commentCount.end(); it++) {
                int t = (it->first == truth);
                int c = (it->first == classifier);
                microtable[t][c]++;
            }
        }
        string judgeComment(string category, string content) {
            vector<string> w = normalSentence(content);
            double Pc, P;
            double maxPwc = - 1e+30;
            string chooseClass = "";
            for (map<string, int>::iterator it = commentCount.begin();
                it != commentCount.end(); it++) {
                Pc = (double)it->second / N;
                P = log(Pc);
                map<string, int> &R = categories[it->first];
                int count_c = count_category[it->first], count_w_c;
                for (int i = 0; i < w.size(); i++) {
                    count_w_c = 0;
                    if (R.find(w[i]) != R.end())
                        count_w_c = R[w[i]];
                    P += log((double) (count_w_c + 1)/ (count_c + R.size()));
                }
                if (P > maxPwc) 
                    maxPwc = P, chooseClass = it->first;
            }
            recordJudge(category, chooseClass);
            return chooseClass;
        }
        void addComment(string category, string content) {
            commentCount[category]++, N++;
            map<string, int> &S = categories[category];
            vector<string> w = normalSentence(content);
            for (int i = 0; i < w.size(); i++)
                S[w[i]]++;
            count_category[category] += w.size(), V += w.size();
        }
        string igntrim(string s) {
            while (s.size() > 0) {
                if (isspace(s[0]) || s[0] == '.' || s[0] == ',' 
                    || s[0] == '!' || s[0] == '"' || s[0] == '\'')
                    s = s.substr(1);
                else {
                    int t = s.length();
                    if (isspace(s[t-1]) || s[t-1] == '.' || s[t-1] == ',' 
                        || s[t-1] == '!' || s[t-1] == '"')
                        s = s.substr(0, t-1);
                    else
                        return s;
                }
            }
            return s;
        }
        string str2lower(string s) {
            for (int i = 0; i < s.length(); i++)
                s[i] = tolower(s[i]);
            return s;
        }
        void custom() {
            set<string> common;
            int first_set = 1;
            for (map<string, map<string, int> >::iterator it = categories.begin();
                it != categories.end(); it++) {
                map<string, int> &R = it->second;
                set<string> s;
                for (map<string, int>::iterator jt = R.begin(); 
                    jt != R.end(); jt++)
                    s.insert(jt->first);
                if (first_set) 	common = s, first_set = 0;
                else {
                    set<string> C;
                    set_intersection(common.begin(), common.end(), s.begin(), s.end(), inserter(C, C.begin()));
                    common = C;
                }
            }
            for (map<string, map<string, int> >::iterator it = categories.begin();
                it != categories.end(); it++) {
                map<string, int> &R = it->second;
                for (set<string>::iterator jt = common.begin();
                    jt != common.end(); jt++)
                    R.erase(*jt);
                int cnt = 0;
                for (map<string, int>::iterator jt = R.begin();
                    jt != R.end(); jt++)
                    cnt += jt->second;
//				printf("%d -> %d\n", count_category[it->first], cnt);
                count_category[it->first] = cnt;
            }
//			printf("%d\n", common.size());
        }
        void print() {
            printf("%-20s+%10s\n", string(20, '-').c_str(), string(10, '-').c_str());
            for (map<string, int>::iterator it = commentCount.begin();
                it != commentCount.end(); it++) {
                printf("%-20s|%10d\n", it->first.c_str(), it->second);
            }
            printf("%-20s+%10s\n", string(20, '-').c_str(), string(10, '-').c_str());
        }
        void report() {
            // print <judge table>
            printf("|%10s|", "AC\\Assign");
            for (map<string, int>::iterator it = commentCount.begin();
                it != commentCount.end(); it++)
                printf("%10s|", it->first.c_str());
            puts("");
            for (map<string, int>::iterator it = commentCount.begin();
                it != commentCount.end(); it++) {
                printf("|%10s|", it->first.c_str());
                for (map<string, int>::iterator jt = commentCount.begin();
                    jt != commentCount.end(); jt++) {
                    printf("%10d|", judgeTable[it->first][jt->first]);
                }
                puts("");
            }
            // homework format
            // recall: fraction of docs in class i classified correctly
            // precision: fraction of docs assigned class i that are actually about class i
            const double beta = 1;
            double micro_r = 0, micro_p = 0, macro_r = 0, macro_p = 0, f1;
            for (map<string, int>::iterator it = commentCount.begin();
                it != commentCount.end(); it++) {
                double recall = 0, precision = 0, f1 = 0;
                int sumr = 0, sump = 0;
                for (map<string, int>::iterator jt = commentCount.begin();
                    jt != commentCount.end(); jt++) {
                    sumr += judgeTable[it->first][jt->first];
                    sump += judgeTable[jt->first][it->first];
                }
                recall = (double) judgeTable[it->first][it->first] / sumr;
                precision = (double) judgeTable[it->first][it->first] / sump;
                f1 = (beta * beta + 1) * precision * recall / (beta * beta * precision + recall);
                
                macro_r += recall, macro_p += precision;
                
                printf("%s\n", it->first.c_str());
                printf("%9s :%.10lf\n", "p", precision);
                printf("%9s :%.10lf\n", "r", recall);
                printf("%9s :%.10lf\n", "f", f1);
            }
//			for (int i = 0; i < 2; i++, puts("")) 
//				for (int j = 0; j < 2; j++)
//					printf("%5d ", microtable[i][j]);
            // [truth 0:1][classifier 0:1] = { {TN, FP}, {FN, TP} } 
            micro_r = (double) microtable[1][1] / (microtable[1][1] + microtable[1][0]); // TP / (TP + FN)
            micro_p = (double) microtable[1][1] / (microtable[1][1] + microtable[1][0]); // TP / (TP + FP)
            f1 = (beta * beta + 1) * micro_p * micro_r / (beta * beta * micro_p + micro_r);
            printf("%s\n", "Micro-average");
            printf("%9s :%.10lf\n", "p", micro_p);
            printf("%9s :%.10lf\n", "r", micro_r);
            printf("%9s :%.10lf\n", "f", f1);
            
            macro_r /= commentCount.size();
            macro_p /= commentCount.size();
            f1 = (beta * beta + 1) * macro_p * macro_r / (beta * beta * macro_p + macro_r);
            printf("%s\n", "Macro-average");
            printf("%9s :%.10lf\n", "p", macro_p);
            printf("%9s :%.10lf\n", "r", macro_r);
            printf("%9s :%.10lf\n", "f", f1);
        }
};
int main() {
    ifstream fin("gold_standard.xml");
    string xml = "", line;
    while (getline(fin, line))
        xml += "\n" + line;
    printf("process gold_standard.xml ...\n");
    
    XMLParser xmlDoc(xml);
    StatsModel statsModel;
    
    printf("statistics model built ...\n");
    for (int i = 0; i < xmlDoc.root.child.size(); i++) {
        string 	a = xmlDoc.root.child[i].attr["category"],
                b = xmlDoc.root.child[i].content;
        statsModel.addComment(a, b);
    }
    
    statsModel.print();
//	statsModel.custom();
    
    ifstream tin("test_outcome.xml");
    
    xml = "";
    while (getline(tin, line))
        xml += "\n" + line;
    printf("process test_outcome.xml ...\n");
    
    XMLParser testDoc(xml);
    
    printf("testing test_outcome.xml ...\n");
    for (int i = 0; i < testDoc.root.child.size(); i++) {
        statsModel.recordJudge(xmlDoc.root.child[i].attr["category"], testDoc.root.child[i].attr["category"]);
    }
    
    statsModel.report();
    
    return 0;
}

#include <stdio.h>
#include <math.h>
int main() {
    int testcase, cases = 0;
    const double pi = acos(-1);
    double D, N, A; 
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%lf %lf", &D, &N);
        A = D / (N - 1);
        double ret = 2 * pi * (A + D);
        printf("Case %d: %.3lf\n", ++cases, ret);
    }
    return 0;
}

#include <stdio.h> 
#include <math.h>
#include <algorithm>
using namespace std;
void gaussianElimination(double mtx[][16], int n, double sol[], int nosol[]) {
#define eps 1e-6
    int i, j;
    for(i = 0; i < n; i++) {
        int k = i;
        for(j = i; j < n; j++)
            if(fabs(mtx[k][i]) < fabs(mtx[j][i]))
                k = j;
        if(fabs(mtx[k][i]) < eps)
            continue;
        if(k != i) {
            for(j = 0; j <= n; j++)
                swap(mtx[k][j], mtx[i][j]);
        }
        for(j = 0; j < n; j++) {
            if(i == j) continue;
            for(k = n; k >= i; k--) {
                mtx[j][k] -= mtx[j][i]/mtx[i][i]*mtx[i][k];
            }
        }
    }
    for(int i = 0; i < n; i++)
        nosol[i] = 0;
    for(i = n-1; i >= 0; i--) {
        if(fabs(mtx[i][i]) < eps)
            nosol[i] = 1;
        else {
            if(fabs(mtx[i][n]) < eps)	sol[i] = 0;
            else						sol[i] = mtx[i][n]/mtx[i][i];
        }
        for(j = i+1; j < n; j++)
            if(fabs(mtx[i][j]) > eps && nosol[j])
            nosol[i] = 1;
    }
}
int main() {
    int testcase, cases = 0;
    double f[16][16], ret[16];
    int sol[16];
    scanf("%d", &testcase);
    while (testcase--) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 4; j++)
                scanf("%lf", &f[i][j]);
        }
        gaussianElimination(f, 3, ret, sol);
        printf("Case %d: %.2lf %.2lf %.2lf\n", ++cases, ret[0], ret[1], ret[2]);
    }
    return 0;
}
/*
2
3 3 1 20.00
6 0 2 20.00
6 4 0 20.00
3 0 1 6.00
0 2 2 10.00
1 3 1 10.00
*/

#include <stdio.h>
#include <algorithm>
#include <set>
using namespace std;
// same 10202 - Pairsumonious Numbers
int main() {
    int n, m, A[50], sum[50];
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while(testcase--) {
    	n = 5;
        m = n*(n-1)/2;
        for(int i = 0; i < m; i++)
            scanf("%d", &sum[i]);
        sort(sum, sum+m);
        
        printf("Case %d:", ++cases);
        multiset<int> oRB;
        for(int i = 2; i < m; i++)
            oRB.insert(sum[i]);
        int idx, flag = 0;
        for(int i = 2; i < m; i++) { // A[1]+A[2] = sum[i]
            if((sum[0]+sum[1]+sum[i])%2)
                continue;
            int tmp = (sum[0]+sum[1]+sum[i])/2;
            A[0] = tmp - sum[i];
            A[1] = tmp - sum[1];
            A[2] = tmp - sum[0];
            multiset<int> RB; // copy
            multiset<int>::iterator it;
            RB = oRB;
            it = RB.find(sum[i]);
            RB.erase(it);
            int pass = 1;
            for(int j = 3; j < n; j++) {
                it = RB.begin();// get min
                A[j] = (*it) - A[0];
                RB.erase(it);
                int ok = 1;
                for(int k = 1; k < j; k++) { // delete A[j]+A[0-(j-1)]
                    int tmp = A[j] + A[k];
                    it = RB.find(tmp);
                    if(it == RB.end()) {
                    	ok = 0;
                    	break;
                    }
                    RB.erase(it);
                }
                if(!ok)	{
                	pass = 0;
                    break;
                }
            }
            if(pass) {// output ans
                flag = 1;
                for(int j = 0; j < n; j++)
                    printf(" %d", A[j]);
                puts("");
                break;
            }
        }
        if(!flag)
            puts("Impossible");
    }
    return 0;
}
/*
3
114 116 118 120 121 122 123 124 125 129
110 111 114 115 118 118 119 122 123 126
180 190 190 196 196 206 216 216 226 232
*/

#include <stdio.h>
#include <math.h>
int main() {
    int testcase, cases = 0;
    double L;
    double u = 1, v = (-2 + sqrt(8))/ 2.0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%lf", &L);
        double time = L / v;
        printf("Case %d: %.2lf\n", ++cases, time * u);
    }
    return 0;
}
/*
army v, courier u
time: 
L / v = L / (u - v) + L / (u + v) => u^2 - v^2 = 2v
result L / v * u, let u = 1 => v = (-2 + sqrt(8))/ 2.0.
*/

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <vector> 
#include <queue>
#include <algorithm>
using namespace std;
vector<int> g[26];
char path[32];
int n, m, st, ed, used[26];
int bused[26] = {}, tused = 0;
int bfs(int u, int comp) {
    tused++;
    int cnt = 0, v;
    queue<int> Q;
    Q.push(u), bused[u] = tused;
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        cnt++;
        for (int i = 0; i < g[u].size(); i++) {
            v = g[u][i];
            if (bused[v] != tused && used[v] == 0) {
                bused[v] = tused;
                Q.push(v);
            }
        }
    }
    return cnt == comp;
}
int dfs(int idx, int u) {
    path[idx] = u + 'A';
    if (idx < n - 1 && used[ed])	return 0;
    if (idx == n-1) {
        path[n] = '\0';
        puts(path);
        return 1;
    }
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (used[v] || !bfs(v, n - idx - 1))	
            continue;
        used[v] = 1;
        if(dfs(idx+1, v))	return 1;
        used[v] = 0;
    }
    return 0;
}
int main() {
    int testcase, cases = 0;
    int x, y;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        char name[26][4], s1[4], s2[4], buf[26];
        int mg[26][26] = {};
        for (int i = 0; i < 26; i++)
            g[i].clear();
        for (int i = 0; i < n; i++)
            scanf("%s", name[i]);
        for (int i = 0; i < m; i++) {
            scanf("%s %s", s1, s2);
            x = s1[0] - 'A', y = s2[0] - 'A';
            mg[x][y] = mg[y][x] = 1;
        }
        st = name[0][0] - 'A', ed = name[n-1][0] - 'A';
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < 26; j++) {
                if (mg[i][j])
                    g[i].push_back(j);
            }
        }
        printf("Case %d: ", ++cases);
        memset(used, 0, sizeof(used));
        used[st] = 1;
        int f = dfs(0, st);
        if (!f)	puts("impossible");
    }
    return 0;
}
/*
3
12 14
A B C D E F U V W X Y Z
A F
A V
B U
B W
C D
C V
D Y
D W
E X
E Z
F U
F Y
U Z
W X
3 2
A B C
A B
A C
50
4 5
L N I K
L N
I L
I N
K N
K I
*/

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
double mrandom() {
    int r = rand();
    return (double) r / RAND_MAX;
}
int main() {
    int n, a, b, c;
    int cases = 0;
    int x[32], y[32], z[32];
    while (scanf("%d", &n) == 1 && n) {
        scanf("%d %d %d", &a, &b, &c);
        const int runtime = 8000000;
        for (int i = 0; i < n; i++)
            scanf("%d %d %d", &x[i], &y[i], &z[i]);
        int count[32] = {}, guess = runtime / n;
        double tx, ty, tz;
        for (int i = guess - 1; i >= 0; i--) {
            tx = mrandom() * a, ty = mrandom() * b, tz = mrandom() * c;
            double dist = 1e+60, tmp;
            int mn = 0;
            for (int j = 0; j < n; j++) {
                tmp = (tx - x[j]) * (tx - x[j]) + (ty - y[j]) * (ty - y[j]) + 
                            (tz - z[j]) * (tz - z[j]);
                if (tmp < dist)
                    dist = tmp, mn = j;
            }
            count[mn]++;
        }
        printf("Case %d:", ++cases);
        for (int i = 0; i < n; i++)
            printf(" %.3lf", (double) count[i] / guess);
        puts("");		
    }
    return 0;
}

#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
int sx, sy, ex, ey, bx, by, cx, cy;
int n, m;
char g[32][32];
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
int dist[25][25][25][25];
int bfs() {
    memset(dist, 0, sizeof(dist));
    dist[sx][sy][bx][by] = 1;
    queue<int> X, Y, BX, BY;
    int x, y, tx, ty, ttx, tty;
    X.push(sx), Y.push(sy), BX.push(bx), BY.push(by);
    while (!X.empty()) {
        x = X.front(), X.pop();
        y = Y.front(), Y.pop();
        bx = BX.front(), BX.pop();
        by = BY.front(), BY.pop();
        int step = dist[x][y][bx][by];
        for (int i = 0; i < 4; i++) {
            tx = x + dx[i], ty = y + dy[i];
            if (tx < 0 || ty < 0 || tx >= n || ty >= m)
                continue;
            if (g[tx][ty] == 'd' && g[bx][by] == 'b')
                return step;
            if (g[tx][ty] == '#' || g[tx][ty] == 'd')
                continue;
            if (tx == bx && ty == by) { // push it
                ttx = tx + dx[i], tty = ty + dy[i];
                if (ttx < 0 || tty < 0 || ttx >= n || tty >= m)
                    continue;
                if (g[ttx][tty] == '#' || g[ttx][tty] == 'd')
                    continue;
                if (dist[tx][ty][ttx][tty] == 0) {
                    dist[tx][ty][ttx][tty] = step + 1;
                    X.push(tx), Y.push(ty), BX.push(ttx), BY.push(tty);
                }
            } else {
                if (dist[tx][ty][bx][by] == 0) {
                    dist[tx][ty][bx][by] = step + 1;
                    X.push(tx), Y.push(ty), BX.push(bx), BY.push(by);
                }
            }
        }
    }
    return -1;
}
int main() {
    while (scanf("%d %d", &n, &m) == 2 && n) {
        for (int i = 0; i < n; i++)
            scanf("%s", g[i]);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g[i][j] == '@')
                    sx = i, sy = j;
                if (g[i][j] == 'd')
                    ex = i, ey = j;
                if (g[i][j] == 'x')
                    bx = i, by = j;
                if (g[i][j] == 'b')
                    cx = i, cy = j;
            }
        }
        int ret = bfs();
        if (ret < 0)	
            puts("No Way!");
        else
            printf("%d\n", ret);
    }
    return 0;
}
/*
3 3
d.b
.@.
x.#
3 5
...d.
.#x#.
...@b
0 0
*/