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 <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto& (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define sar(a,n) cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl
#define svec(v) cout<<#v<<":";rep(pachico,v.size())cout<<" "<<v[pachico];cout<<endl
#define svecp(v) cout<<#v<<":";each(pachico,v)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl
#define sset(s) cout<<#s<<":";each(pachico,s)cout<<" "<<pachico;cout<<endl
#define smap(m) cout<<#m<<":";each(pachico,m)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl

using namespace std;

typedef pair<int,int> P;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<P> vp;
typedef vector<string> vs;

const int MAX_N = 50;

const int dx[] = {1,0,0,-1};
const int dy[] = {0,1,-1,0};

struct tri
{
    int x,y,z;
    tri(){}
    tri(int x_, int y_, int z_) : x(x_), y(y_), z(z_){}
};

int h,w;
string s[MAX_N];
int dist[MAX_N][MAX_N];
int cs[MAX_N][MAX_N][4];
int memo[MAX_N][MAX_N][5][4];

int move(int a, int b, int c, int d)
{
    rep(i,h){
        rep(j,w){
            dist[i][j] = INF;
        }
    }
    queue<P> que;
    dist[a][b] = 0;
    que.push(P(a,b));
    while(!que.empty()){
        P p = que.front();
        que.pop();
        rep(i,4){
            int nx = p.fi + dx[i], ny = p.se + dy[i];
            if(nx >= 0 && nx < h && ny >= 0 && ny < w && s[nx][ny] != '*' && dist[nx][ny] > dist[p.fi][p.se] + 1){
                dist[nx][ny] = dist[p.fi][p.se] + 1;
                if(nx == c && ny == d) return dist[c][d];
                que.push(P(nx,ny));
            }
        }
    }
    return dist[c][d];
}

int calc(int a1, int b1, int a2, int b2, int c1, int d1, int c2, int d2)
{
    int res = INF;
    int res1, res2;
    
    s[a2][b2] = '*';
    res1 = move(a1,b1,c1,d1);
    s[c1][d1] = '*';
    res2 = move(a2,b2,c2,d2);
    s[a2][b2] = s[c1][d1] = 'o';
    cmn(res,res1+res2);
    
    s[a2][b2] = '*';
    res1 = move(a1,b1,c2,d2);
    s[c2][d2] = '*';
    res2 = move(a2,b2,c1,d1);
    s[a2][b2] = s[c2][d2] = 'o';
    cmn(res,res1+res2);
    
    s[a1][b1] = '*';
    res1 = move(a2,b2,c1,d1);
    s[c1][d1] = '*';
    res2 = move(a1,b1,c2,d2);
    s[a1][b1] = s[c1][d1] = 'o';
    cmn(res,res1+res2);
    
    s[a1][b1] = '*';
    res1 = move(a2,b2,c2,d2);
    s[c2][d2] = '*';
    res2 = move(a1,b1,c1,d1);
    s[a1][b1] = s[c2][d2] = 'o';
    cmn(res,res1+res2);
    
    return res;
}

// king が (px,py) にあって (x1,y1), (x2,y2) に空きがある
void solve(int px, int py, int pz, int x1, int y1, int x2, int y2, int cost, queue<tri>& que)
{
    rep(i,2){
        rep(j,2){
            s[px+i][py+j] = '*';
        }
    }
    // cout << px << " " << py << "\n";
    // print();
    int nx = px + dx[0], ny = py + dy[0];
    if(nx < h-1 && s[nx+1][ny] != '*' && s[nx+1][ny+1] != '*'){
        int d;
        if(memo[px][py][pz][0] >= 0){
            d = memo[px][py][pz][0];
        }else{
            memo[px][py][pz][0] = d = calc(x1,y1,x2,y2,nx+1,ny,nx+1,ny+1);
        }
        if(cs[nx][ny][0] > cost + d + 1){
            cs[nx][ny][0] = cost + d + 1;
            que.push(tri(nx,ny,0));
        }
    }
    nx = px + dx[1], ny = py + dy[1];
    if(ny < w-1 && s[nx][ny+1] != '*' && s[nx+1][ny+1] != '*'){
        int d;
        if(memo[px][py][pz][1] >= 0){
            d = memo[px][py][pz][1];
        }else{
            memo[px][py][pz][1] = d = calc(x1,y1,x2,y2,nx,ny+1,nx+1,ny+1);
        }
        if(cs[nx][ny][1] > cost + d + 1){
            cs[nx][ny][1] = cost + d + 1;
            que.push(tri(nx,ny,1));
        }
    }
    nx = px + dx[2], ny = py + dy[2];
    if(ny >= 0 && s[nx][ny] != '*' && s[nx+1][ny] != '*'){
        int d;
        if(memo[px][py][pz][2] >= 0){
            d = memo[px][py][pz][2];
        }else{
            memo[px][py][pz][2] = d = calc(x1,y1,x2,y2,nx,ny,nx+1,ny);
        }
        if(cs[nx][ny][2] > cost + d + 1){
            cs[nx][ny][2] = cost + d + 1;
            que.push(tri(nx,ny,2));
        }
    }
    nx = px + dx[3], ny = py + dy[3];
    if(nx >= 0 && s[nx][ny] != '*' && s[nx][ny+1] != '*'){
        int d;
        if(memo[px][py][pz][3] >= 0){
            d = memo[px][py][pz][3];
        }else{
            memo[px][py][pz][3] = d = calc(x1,y1,x2,y2,nx,ny,nx,ny+1);
        }
        if(cs[nx][ny][3] > cost + d + 1){
            cs[nx][ny][3] = cost + d + 1;
            que.push(tri(nx,ny,3));
        }
    }
    
    rep(i,2){
        rep(j,2){
            s[px+i][py+j] = 'o';
        }
    }
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    while(1){
        cin >> h >> w;
        if(h == 0) break;
        bool flag = false;
        int sth, stw;
        int a = -1,b,c,d;
        rep(i,h){
            cin >> s[i];
            rep(j,w){
                if(s[i][j] == 'X'){
                    if(!flag){
                        sth = i, stw = j;
                        flag = true;
                    }
                    s[i][j] = 'o';
                }else if(s[i][j] == '.'){
                    if(a < 0){
                        a = i, b = j;
                    }else{
                        c = i, d = j;
                    }
                    s[i][j] = 'o';
                }
                rep(k,4){
                    cs[i][j][k] = INF;
                }
                rep(k,5){
                    rep(l,4){
                        memo[i][j][k][l] = -1;
                    }
                }
            }
        }
        if(sth == 0 && stw == 0){
            cout << "0\n";
            continue;
        }
        queue<tri> que;
        solve(sth,stw,4,a,b,c,d,0,que);
        while(!que.empty()){
            tri p = que.front();
            que.pop();
            int a,b,c,d;
            if(p.z == 0){
                a = p.x-1, b = p.y, c = p.x-1, d = p.y+1;
            }else if(p.z == 1){
                a = p.x, b = p.y-1, c = p.x+1, d = p.y-1;
            }else if(p.z == 2){
                a = p.x, b = p.y+2, c = p.x+1, d = p.y+2;
            }else{
                a = p.x+2, b = p.y, c = p.x+2, d = p.y+1;
            }
            solve(p.x,p.y,p.z,a,b,c,d,cs[p.x][p.y][p.z],que);
        }
        int res = INF;
        rep(i,4){
            cmn(res,cs[0][0][i]);
        }
        if(res == INF){
            cout << "-1\n";
        }else{
            cout << res << "\n";
        }
    }
    return 0;
}