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<cstdio>
#include<vector>
#include<map>
#include<utility>
#include<queue>
#include<algorithm>

using namespace std;

typedef pair<int,int> P;
typedef vector<P> Stat;

const int inf=1e8;

const int di[]={0,-1,0,1},dj[]={1,0,-1,0};
const int di2[4][2]={{0,1},{-1,-1},{0,1},{2,2}};
const int dj2[4][2]={{2,2},{0,1},{-1,-1},{0,1}};

char field[55][55];
int W,H;
P stKing,p1,p2;
char ch[55];

int dis[55][55];
void bfs(P king,P st){
	for(int i=0;i<55;i++) for(int j=0;j<55;j++) dis[i][j]=inf;
	int i0=king.first,j0=king.second;
	for(int i=0;i<=1;i++) for(int j=0;j<=1;j++){
		field[i0+i][j0+j]='*';
	}
	queue<int> qi,qj;
	qi.push(st.first);
	qj.push(st.second);
	dis[st.first][st.second]=0;
	while(!qi.empty()){
		int ci=qi.front(),cj=qj.front();
		qi.pop();qj.pop();
		int cd=dis[ci][cj];
		for(int i=0;i<4;i++){
			int ni=ci+di[i],nj=cj+dj[i];
			if(field[ni][nj]=='*') continue;
			if(dis[ni][nj]<=cd+1) continue;
			dis[ni][nj]=cd+1;
			qi.push(ni);qj.push(nj);
		}
	}
//	if(king==P(2,2)&&st==P(1,3)){
//		for(int i=1;i<=3;i++){
//			for(int j=1;j<=3;j++) printf("%d ",dis[i][j]);
//			printf("\n");
//		}
//	}
	for(int i=0;i<=1;i++) for(int j=0;j<=1;j++){
		field[i0+i][j0+j]='o';
	}
}

int getD(P king,P p1,P p2,P q1,P q2){
//	printf("%d %d %d %d %d %d %d %d %d %d\n",king.first,king.second,p1.first,p1.second,
//		p2.first,p2.second,q1.first,q1.second,q2.first,q2.second);
	int res=inf;
	int tmp1=0,tmp2=0;
	bfs(king,p1);
	int i1=q1.first,j1=q1.second;
	int i2=q2.first,j2=q2.second;
//	if(king==P(2,2)&&p1==P(1,3)){
//		printf("--- %d %d %d %d --\n",i1,j1,i2,j2);
//	}
	tmp1+=dis[i1][j1];
	tmp2+=dis[i2][j2];
//	printf("%d %d\n",dis[i1][j1],dis[i2][j2]);
	bfs(king,p2);
	tmp1+=dis[i2][j2];
	tmp2+=dis[i1][j1];
//	printf("%d %d\n",dis[i2][j2],dis[i1][j1]);
	res=min(res,tmp1);
	res=min(res,tmp2);
	return res;
}

vector<P> getAdj(P king,int dir){
	vector<P> res;
//	printf("%d %d %d\n",king.first,king.second,dir);
	for(int i=0;i<2;i++){
		res.push_back(king);
		res[i].first+=di2[dir][i];
		res[i].second+=dj2[dir][i];
//		printf("%d %d\n",res[i].first,res[i].second);
	}
	return res;
}

bool isvalid(P king,P p1,P p2){
	for(int i=0;i<2;i++) for(int j=0;j<2;j++){
		if(field[king.first+i][king.second+j]=='*') return false;
	}
	if(field[p1.first][p1.second]=='*') return false;
	if(field[p2.first][p2.second]=='*') return false;
	return true;
}

bool isvalid(Stat s){
	return isvalid(s[0],s[1],s[2]);
}

vector<Stat> stats;

struct edge{
	int to,cost;
	edge(){}
	edge(int a,int b):to(a),cost(b){}
};

vector<edge> G[20200];
int dis2[20200];

void print(Stat s){
	for(int i=0;i<3;i++){
		printf("%d %d ",s[i].first,s[i].second);
	}
	printf("\n");
}

void getGraph(){
//	printf("getGraph\n");
	Stat ini;
	ini.push_back(stKing);
	ini.push_back(p1);
	ini.push_back(p2);
	stats.push_back(ini);
//	print(ini);
	for(int i=1;i<H;i++) for(int j=1;j<W;j++){
		for(int k=0;k<4;k++){
			vector<P> emp=getAdj(P(i,j),k);
			vector<P> cur;
			cur.push_back(P(i,j));
			for(int t=0;t<2;t++) cur.push_back(emp[t]);
			if(isvalid(cur)==false) continue;
			stats.push_back(cur);
//			print(cur);
		}
	}
	for(int i=0;i<stats.size();i++) for(int j=0;j<stats.size();j++){
		if(i==j) continue;
		Stat st1=stats[i],st2=stats[j];
		if(abs(st1[0].first-st2[0].first)+abs(st1[0].second-st2[0].second)==0){
			int d=getD(st1[0],st1[1],st1[2],st2[1],st2[2]);
			G[i].push_back(edge(j,d));
//			printf("%d->%d %d\n",i,j,d);
		}
		else if(abs(st1[0].first-st2[0].first)+abs(st1[0].second-st2[0].second)==1){
			vector<P> tmp1,tmp2;
			for(int k=0;k<2;k++) for(int m=0;m<2;m++){
				tmp1.push_back(P(st1[0].first+k,st1[0].second+m));
				tmp2.push_back(P(st2[0].first+k,st2[0].second+m));
			}
			for(int k=1;k<=2;k++) tmp1.push_back(st1[k]);
			for(int k=1;k<=2;k++) tmp2.push_back(st2[k]);
			sort(tmp1.begin(),tmp1.end());
			sort(tmp2.begin(),tmp2.end());
			if(tmp1==tmp2){
				G[i].push_back(edge(j,1));
//				printf("%d->%d %d\n",i,j,1);
			}
		}
	}
}

void dijkstra(int s){
	for(int i=0;i<20200;i++) dis2[i]=inf;
	dis2[s]=0;
	priority_queue<P,vector<P>,greater<P> > que;
	que.push(P(0,s));
	while(!que.empty()){
		P p=que.top();
		que.pop();
		int v=p.second;
		int d=p.first;
		if(dis2[v]<d) continue;
		for(int i=0;i<G[v].size();i++){
			int nv=G[v][i].to;
			int nd=d+G[v][i].cost;
			if(dis2[nv]<=nd) continue;
			dis2[nv]=nd;
			que.push(P(nd,nv));
		}
	}
}

void init(){
	for(int i=0;i<20200;i++) G[i].clear();
	stats.clear();
}

int main(){
	int testnum=0;
	while(true){
		scanf("%d%d",&H,&W);
		if(H+W==0) break;
		for(int i=0;i<55;i++) for(int j=0;j<55;j++) field[i][j]='*';
		for(int i=0;i<H;i++){
			scanf("%s",ch);
			for(int j=0;j<W;j++) field[i+1][j+1]=ch[j];
		}
		for(int i=1;i<=H;i++) for(int j=1;j<=W;j++){
			if(field[i][j]=='X'){
				stKing=P(i,j);
				goto ed;
			}
		}
		ed:;
		p1=P(-1,-1);
		for(int i=1;i<=H;i++) for(int j=1;j<=W;j++){
			if(field[i][j]!='.') continue;
			if(p1==P(-1,-1)) p1=P(i,j);
			else p2=P(i,j);
		}
		init();
		getGraph();
		dijkstra(0);
		int ans=inf;
		for(int i=0;i<stats.size();i++){
			if(stats[i][0]==P(1,1)){
				ans=min(ans,dis2[i]);
			}
		}
		if(ans==inf) printf("-1\n");
		else printf("%d\n",ans);
//		if(testnum<100){
//			printf("%d %d\n",stats[0][0].first,stats[0][0].second);
//		}
//		break;
		testnum++;
	}
	return 0;
}