Problem: In sliding block puzzles, we repeatedly slide pieces (blocks) to open spaces within a frame to establish a goal placement of pieces.

A puzzle creator has designed a new puzzle by combining the ideas of sliding block puzzles and mazes. The puzzle is played in a rectangular frame segmented into unit squares. Some squares are pre-occupied by obstacles. There are a number of pieces placed in the frame, one 2 × 2 king piece and some number of 1 × 1 pawn pieces. Exactly two 1 × 1 squares are left open. If a pawn piece is adjacent to an open square, we can slide the piece there. If a whole edge of the king piece is adjacent to two open squares, we can slide the king piece. We cannot move the obstacles. Starting from a given initial placement, the objective of the puzzle is to move the king piece to the upper-left corner of the frame.

The following figure illustrates the initial placement of the fourth dataset of the sample input.

<image>


Figure E.1: The fourth dataset of the sample input.

Your task is to write a program that computes the minimum number of moves to solve the puzzle from a given placement of pieces. Here, one move means sliding either king or pawn piece to an adjacent position.



Input

The input is a sequence of datasets. The first line of a dataset consists of two integers H and W separated by a space, where H and W are the height and the width of the frame. The following H lines, each consisting of W characters, denote the initial placement of pieces. In those H lines, 'X', 'o', '*', and '.' denote a part of the king piece, a pawn piece, an obstacle, and an open square, respectively. There are no other characters in those H lines. You may assume that 3 ≤ H ≤ 50 and 3 ≤ W ≤ 50.

A line containing two zeros separated by a space indicates the end of the input.

Output

For each dataset, output a line containing the minimum number of moves required to move the king piece to the upper-left corner. If there is no way to do so, output -1.

Example

Input

3 3
oo.
oXX
.XX
3 3
XXo
XX.
o.o
3 5
.o*XX
oooXX
oooo.
7 12
oooooooooooo
ooooo*****oo
oooooo****oo
o**ooo***ooo
o***ooooo..o
o**ooooooXXo
ooooo****XXo
5 30
oooooooooooooooooooooooooooooo
oooooooooooooooooooooooooooooo
o***************************oo
XX.ooooooooooooooooooooooooooo
XX.ooooooooooooooooooooooooooo
0 0


Output

11
0
-1
382
6807

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <array>

using namespace std;

enum CellType {
    CELL_EMPTY,
    CELL_PAWN,
    CELL_BLOCK,
    CELL_KING
};
typedef pair<int,int> Point;
typedef unsigned int State;
typedef long long LL;

const LL INF = 50LL*50*2*50*50*100;
const Point SPACE_POS[4][2] = {
    {Point(0, 2), Point(1, 2)},
    {Point(-1, 1), Point(-1, 0)},
    {Point(0, -1), Point(1, -1)},
    {Point(2, 0), Point(2, 1)}
};
const Point DELTA[] = {
    Point(0, 1),
    Point(-1, 0),
    Point(0, -1),
    Point(1, 0)
};
const int MOVED[] = {
    2, 3, 0, 1
};

int H, W;
array<array<CellType,55>,55> field;

ostream& operator <<(ostream &os, const Point &p) {
    return os << "(" << p.first << "," << p.second << ")";
}
Point operator +(const Point &a, const Point &b) {
    return Point(a.first+b.first, a.second+b.second);
}

State encode(const Point &king, int dir) {
    return ((king.first*55)+king.second)*55 + dir;
}

// Return: (king position, dir)
pair<Point,int> decode(State s) {
    unsigned int dir = s % 55;
    s /= 55;
    Point king(s/55, s%55);
    for(int i = 0; i <= H+1; ++i) {
        for(int j = 0; j <= W+1; ++j) {
            if(field[i][j] != CELL_BLOCK) field[i][j] = CELL_PAWN;
        }
    }
    field[king.first][king.second] = CELL_KING;
    field[king.first+1][king.second] = CELL_KING;
    field[king.first][king.second+1] = CELL_KING;
    field[king.first+1][king.second+1] = CELL_KING;
    /*
    for(int r = 0; r <= H+1; ++r) {
        for(int c = 0; c <= W+1; ++c) {
            cout << field[r][c];
        }
        cout << endl;
    }
    cout << dir << endl;
    */
    return make_pair(king, dir);
}

array<array<bool,55>,55> bfs_visited;
LL bfs(Point start, Point goal) {
    for(int i = 0; i < 55; ++i) {
        for(int j = 0; j < 55; ++j) {
            bfs_visited[i][j] = false;
        }
    }
    static vector<Point> q[2];
    q[0].clear();
    q[0].push_back(start);
    bfs_visited[start.first][start.second] = true;
    //cout << start << "," << goal << endl;
    for(int turn = 0; q[0].size() > 0; ++turn) {
        q[1].clear();
        for(const Point &p : q[0]) {
            //cout << p << endl;
            if(p == goal) return turn;
            for(int i = 0; i < 4; ++i) {
                const Point np = p + DELTA[i];
                if(field[np.first][np.second] != CELL_PAWN) continue;
                if(bfs_visited[np.first][np.second]) continue;
                bfs_visited[np.first][np.second] = true;
                q[1].push_back(np);
            }
        }
        q[0].swap(q[1]);
    }
    return INF;
}

vector<pair<LL,State>> load() {
    Point king;
    bool king_found = false;
    for(int i = 0; i < 55; ++i) {
        for(int j = 0; j < 55; ++j) {
            field[i][j] = CELL_BLOCK;
        }
    }
    vector<Point> empty_cells;
    for(int i = 1; i <= H; ++i) {
        string str;
        cin >> str;
        for(int j = 1; j <= W; ++j) {
            if(str[j-1] == 'o') {
                field[i][j] = CELL_PAWN;
            } else if(str[j-1] == '.') {
                field[i][j] = CELL_PAWN;
                empty_cells.push_back(Point(i, j));
            } else if(str[j-1] == '*') {
                field[i][j] = CELL_BLOCK;
            } else if(str[j-1] == 'X' && !king_found) {
                king_found = true;
                king = Point(i, j);
                field[i][j] = CELL_KING;
                field[i+1][j] = CELL_KING;
                field[i][j+1] = CELL_KING;
                field[i+1][j+1] = CELL_KING;
            }
        }
    }
    vector<pair<LL,State>> res;
    if(king == Point(1, 1)) {
        res.push_back(make_pair(1, 0));
        return res;
    }
    for(int dir = 0; dir < 4; ++dir) {
        const Point p1 = king + SPACE_POS[dir][0];
        const Point p2 = king + SPACE_POS[dir][1];
        if(field[p1.first][p1.second] == CELL_BLOCK) continue;
        if(field[p2.first][p2.second] == CELL_BLOCK) continue;
        //cout << p1 << " " << p2 << endl;
        LL fastest = min(bfs(p1, empty_cells[0]) + bfs(p2, empty_cells[1]), bfs(p1, empty_cells[1]) + bfs(p2, empty_cells[0]));
        if(fastest >= INF) continue;
        res.push_back(make_pair(-fastest, encode(king, dir)));
    }
    return res;
}

array<LL,((((55*55)+55)*55)+4)> memo;
bool solve() {
    cin >> H >> W;
    if(!H && !W) return false;
    vector<pair<LL,State>> initial = load();
    fill(memo.begin(), memo.end(), INF);

    priority_queue<pair<LL,State>> q;
    for(const auto &s : initial) {
        if(s.first > 0) {
            cout << 0 << endl;
            return true;
        }
        q.push(s);
        memo[s.second] = -s.first;
    }
    while(!q.empty()) {
        LL cost = -q.top().first;
        State cur = q.top().second;
        q.pop();
        if(cost > memo[cur]) continue;
        //cout << cur << endl;
        const pair<Point,int> state = decode(cur);
        const int dir = state.second;
        const Point p1 = state.first + SPACE_POS[dir][0];
        const Point p2 = state.first + SPACE_POS[dir][1];
        //cout << cost << endl;
        //cout << state.first << ' ' << p1 << ' ' << p2 << endl;
        if(state.first == Point(1, 1)) {
            cout << cost << endl;
            return true;
        }

        // to-dir
        for(int i = 0; i < 4; ++i) {
            const Point np1 = state.first + SPACE_POS[i][0];
            const Point np2 = state.first + SPACE_POS[i][1];
            if(field[np1.first][np1.second] == CELL_BLOCK) continue;
            if(field[np2.first][np2.second] == CELL_BLOCK) continue;
            LL fastest = min(bfs(np1, p1) + bfs(np2, p2), bfs(np1, p2) + bfs(np2, p1));
            if(fastest >= INF) continue;
            const LL nc = cost + fastest + 1;
            const State ns = encode(state.first + DELTA[i], MOVED[i]);
            if(memo[ns] <= nc) continue;
            memo[ns] = nc;
            q.push(make_pair(-nc, ns));
            //cout << ns << state.first+DELTA[i] << MOVED[i] << endl;
        }
    }
    cout << -1 << endl;
    return true;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    while(solve()) ;
    return 0;
}