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 <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#include <functional>
#include <map>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define rep1(i,n) for(int i=1;i<=(n);++i)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define miz(x,y) x=min(x,y)
typedef pair<int,int> P;
struct state{
	int x,y,di;
	bool operator < (const state& r) const{
		if(x!=r.x) return x<r.x;
		if(y!=r.y) return y<r.y;
		return di<r.di;
	}
};
struct edge{
	state to;
	int cost;
};
typedef pair<int,state> pa;
map<state,vector<edge> > mp;
int H,W,dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int ddx[8]={2,2,1,0,-1,-1,0,1};
int ddy[8]={0,1,2,2,1,0,-1,-1};
int inf=1e8;
string board[50];
bool is(int x,int y){
	if(x<0||H<=x||y<0||W<=y) return false;
	if(board[x][y]=='*') return false;
	return true;
}
int calcd(P s,P t,vector<P> vc){
	queue<P> que;
	int d[50][50]={};
	rep(i,H) rep(j,W) d[i][j]=inf;
	que.push(s);
	d[s.fs][s.sc]=0;
	while(!que.empty()){
		P p=que.front();
		que.pop();
		if(p==t) break;
		int x=p.fs,y=p.sc;
		rep(j,4){
			int nx=x+dx[j],ny=y+dy[j];
			if(d[nx][ny]!=inf) continue;
			bool can=is(nx,ny);
			rep(k,4) if(nx==vc[k].fs&&ny==vc[k].sc) can=false;
			if(!can) continue;
			que.push(P(nx,ny));
			d[nx][ny]=d[x][y]+1;
		}
	}
	return d[t.fs][t.sc];
}
int calccost(int x,int y,int d1,int d2){
	int ret=inf;
	vector<P> banned;
	rep(i,2) rep(j,2) banned.pb(P(x+i,y+j));
	P s1=P(x+ddx[d1*2],y+ddy[d1*2]);
	P s2=P(x+ddx[d1*2+1],y+ddy[d1*2+1]);
	P t1=P(x+ddx[d2*2],y+ddy[d2*2]);
	P t2=P(x+ddx[d2*2+1],y+ddy[d2*2+1]);
	miz(ret,calcd(s1,t1,banned)+calcd(s2,t2,banned));
	miz(ret,calcd(s1,t2,banned)+calcd(s2,t1,banned));
	return ret;
}
int calccost2(int x,int y,int di,P s1,P s2){
	int ret=inf;
	vector<P> banned;
	rep(i,2) rep(j,2) banned.pb(P(x+i,y+j));
	P t1=P(x+ddx[di*2],y+ddy[di*2]);
	P t2=P(x+ddx[di*2+1],y+ddy[di*2+1]);
	miz(ret,calcd(s1,t1,banned)+calcd(s2,t2,banned));
	miz(ret,calcd(s1,t2,banned)+calcd(s2,t1,banned));
	return ret;
}
bool canput(int x,int y,int di){
	return is(x+ddx[di*2],y+ddy[di*2])&&is(x+ddx[di*2+1],y+ddy[di*2+1]);
}
priority_queue<pa,vector<pa>,greater<pa> > que;
map<state,int> d;
int main(){
	while(true){
		mp.clear();
		cin>>H>>W;
		if(H==0) break;
		rep(i,H) cin>>board[i];
		rep(i,H-1) rep(j,W-1){
			bool king=true;
			rep(k1,2) rep(k2,2) if(!is(i+k1,j+k2)) king=false;
			if(!king) continue;
//			show(i);
//			show(j);
			rep(d1,4){
//				if(i==1&&j==0) show(d1);
				if( !canput(i,j,d1) ) continue;
				rep(d2,4){
					if(d1==d2) continue;
					if( !canput(i,j,d2) ) continue;
//					if(i==1&&j==0&&d1==1) show(d2);
					int cost=calccost(i,j,d1,d2);
					if(cost!=inf){
						mp[state{i,j,d1}].pb(edge{state{i,j,d2},cost});
//						printf("i=%d, j=%d, d1=%d, d2=%d  cost=%d\n",i,j,d1,d2,cost);
					}
				}
			}
		}
		rep(i,H-1) rep(j,W-1) rep(di,4){
			if( !canput(i,j,di) ) continue;
			mp[state{i,j,di}].pb(edge{state{i+dx[di],j+dy[di],(di+2)%4},1});
//			printf("i=%d, j=%d, di=%d,  -> %d %d %d\n",i,j,di,i+dx[di],j+dy[di],(di+2)%4);
		}
		while(!que.empty()) que.pop();
		d.clear();
		int sx,sy;
		P s1,s2;
		int cnt=0;
		rep(i,H) rep(j,W) if(board[i][j]=='X'){
			sx=i,sy=j;
			goto br;
		}
		br:
		if(sx==0&&sy==0){
			puts("0");
			continue;
		}
		rep(i,H) rep(j,W) if(board[i][j]=='.'){
			if(cnt==0) s1=P(i,j),cnt++;
			else s2=P(i,j);
		}
		rep(di,4){
			if(!canput(sx,sy,di)) continue;
			int cost=calccost2(sx,sy,di,s1,s2);
			if(cost!=inf){
				que.push(pa(cost,state{sx,sy,di}));
				d[state{sx,sy,di}]=cost;
//				show(sx);
//				show(sy);
//				show(di);
//				show(cost);
//				cout<<endl;
			}
		}
		while(!que.empty()){
			pa pat=que.top();
			que.pop();
			state st=pat.sc;
			int dist=pat.fs;
			if(d[st]<dist) continue;
			for(auto e : mp[st]){
				if(d.find(e.to)==d.end()||d[e.to]>d[st]+e.cost){
					d[e.to]=d[st]+e.cost;
					que.push(pa(d[e.to],e.to));
//					show(e.to.x);
//					show(e.to.y);
//					show(e.to.di);
//					cout<<endl;
				}
			}
		}
		int ans=inf;
		state start=state{0,0,0};
		if(d.find(start)!=d.end()) miz(ans,d[start]);
		start=state{0,0,1};
		if(d.find(start)!=d.end()) miz(ans,d[start]);
		if(ans==inf) ans=-1;
		cout<<ans<<endl;
	}
}