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 <cstring>
#include <iostream>
#include <utility>
#include <queue>
#include <string>
#define INF 1e7
using namespace std;
typedef pair<int,int> P;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int ddx[4][2]={
	2,2,
	0,1,
	-1,-1,
	0,1
};
int ddy[4][2]={
	0,1,
	2,2,
	0,1,
	-1,-1
};
P operator +(P p1,P p2){
	return P(p1.first+p2.first,p1.second+p2.second);
}
P operator -(P p1,P p2){
	return P(p1.first-p2.first,p1.second-p2.second);
}

int h,w;
int fie[51][51];
struct data{
	int cost,pdir;
	P k;
	data(){}
	data(P kk,int cc,int pp){
		k=kk;
		cost=cc;
		pdir=pp;
	}
	bool operator<(const data &d1)const{
		if(cost!=d1.cost)return cost>d1.cost;
		if(k!=d1.k)return k>d1.k;
		return pdir>d1.pdir;
	}
};

struct data2{
	P k,o[2];
	data2(){}
	data2(P kk,P o1,P o2){
		k=kk;
		o[0]=o1;
		o[1]=o2;
	}
};

bool cross(P a,P b){
	if(a==b)return true;
	if(a==(b+P(1,0)))return true;
	if(a==(b+P(0,1)))return true;
	if(a==(b+P(1,1)))return true;
	return false;
}

bool canmove(P a){
	if(a.first>=0 && a.first<w && a.second>=0 && a.second<h)return true;
	return false;
}

bool same(P a,P b){
	return a.first==b.first && a.second==b.second;
}

bool same(data2 a,data2 b){
	if(!same(a.k,b.k))return false;
	if(!same(a.o[0],b.o[0]))return false;
	if(!same(a.o[1],b.o[1]))return false;
	return true;
}

int distp[51][51];
int move_pawn(P f,P t){
	for(int i=0;i<50;i++){
		for(int j=0;j<50;j++){
			distp[i][j]=INF;
		}
	}
	queue<P> que;
	que.push(f);
	distp[f.first][f.second]=0;
	while(que.size()){
		P q=que.front();
		que.pop();
		if(q==t)return distp[q.first][q.second];
		for(int i=0;i<4;i++){
			P nq=q+P(dy[i],dx[i]);
			if(nq.first>=0 && nq.first<h && nq.second>=0 && nq.second<w){
				if(distp[nq.first][nq.second]==INF && fie[nq.first][nq.second]!=-1){
					distp[nq.first][nq.second]=distp[q.first][q.second]+1;
					que.push(P(nq));
				}
			}
		}
	}
	return INF;
}

data first_moveking(P k,P o1,P o2,int dir){
	data res;
	fie[k.first][k.second]=-1;
	fie[k.first+1][k.second]=-1;
	fie[k.first][k.second+1]=-1;
	fie[k.first+1][k.second+1]=-1;
	int cost1=move_pawn(o1,k+P(ddy[dir][0],ddx[dir][0]))+move_pawn(o2,k+P(ddy[dir][1],ddx[dir][1]));
	int cost2=move_pawn(o1,k+P(ddy[dir][1],ddx[dir][1]))+move_pawn(o2,k+P(ddy[dir][0],ddx[dir][0]));
	res.cost=min(cost1,cost2)+1;
	fie[k.first][k.second]=0;
	fie[k.first+1][k.second]=0;
	fie[k.first][k.second+1]=0;
	fie[k.first+1][k.second+1]=0;
	res.pdir=dir;
	res.k=k+P(dy[dir],dx[dir]);
	return res;
}

data moveking(data q,int dir){
	data res;
	P k=q.k;
	fie[k.first][k.second]=-1;
	fie[k.first+1][k.second]=-1;
	fie[k.first][k.second+1]=-1;
	fie[k.first+1][k.second+1]=-1;
	P o1=k+P(ddy[(q.pdir+2)%4][0],ddx[(q.pdir+2)%4][0]);
	P o2=k+P(ddy[(q.pdir+2)%4][1],ddx[(q.pdir+2)%4][1]);
	//printf("y%d x%d y%d x%d dir%d\n",o1.second,o1.first,o2.second,o2.first,dir);
	int cost1=move_pawn(o1,k+P(ddy[dir][0],ddx[dir][0]))+move_pawn(o2,k+P(ddy[dir][1],ddx[dir][1]));
	int cost2=move_pawn(o1,k+P(ddy[dir][1],ddx[dir][1]))+move_pawn(o2,k+P(ddy[dir][0],ddx[dir][0]));
	//printf("ox%d oy%d ox%d oy%d\n",k.second+ddx[dir][0],k.first+ddy[dir][0],k.second+ddx[dir][1],k.first+ddy[dir][1]);
	//printf("c%d c%d %d %d\n",cost1,cost2,k.second+dx[dir],k.first+dy[dir]);
	res.cost=min(cost1,cost2)+1+q.cost;
	fie[k.first][k.second]=0;
	fie[k.first+1][k.second]=0;
	fie[k.first][k.second+1]=0;
	fie[k.first+1][k.second+1]=0;
	res.pdir=dir;
	res.k=k+P(dy[dir],dx[dir]);
	return res;
}

int dist[51][51][4];
int dijkstra(P s,P o1,P o2){
	priority_queue<data> que;
	for(int i=0;i<50;i++){
		for(int j=0;j<50;j++){
			for(int k=0;k<4;k++){
				dist[i][j][k]=INF;
			}
		}
	}
	for(int i=0;i<4;i++){
		if(s.second+dx[i]>=0 && s.second+dx[i]<w-1 && s.first+dy[i]>=0 && s.first+dy[i]<h-1){
			data si=first_moveking(s,o1,o2,i);
			if(si.cost<INF){
				que.push(si);
				dist[si.k.first][si.k.second][si.pdir]=si.cost;
			}
		}
	}
	while(que.size()){
		data q=que.top();
		que.pop();
		if(q.cost>dist[q.k.first][q.k.second][q.pdir])continue;
		//printf("%d %d\n",q.k.first,q.k.second);
		if(q.k.first+q.k.second==0)return q.cost;
		for(int i=0;i<4;i++){
			if(q.k.second+dx[i]>=0 && q.k.second+dx[i]<w-1 && q.k.first+dy[i]>=0 && q.k.first+dy[i]<h-1){
				data nq=moveking(q,i);
				if(nq.cost<dist[nq.k.first][nq.k.second][nq.pdir]){
					dist[nq.k.first][nq.k.second][nq.pdir]=nq.cost;
					que.push(nq);
					//printf("%d %d %d\n",nq.cost,nq.k.second,nq.k.first);
				}
			}
		}
	}
	return -1;
}

int main(void){
	while(1){
		scanf("%d %d",&h,&w);
		if(h+w==0)break;
		P k,o[2];
		k.first=k.second=-1;
		int cnt=0;
		memset(fie,0,sizeof(fie));
		for(int i=0;i<h;i++){
			string str;
			cin >> str;
			for(int j=0;j<w;j++){
				if(str[j]=='*')fie[i][j]=-1;
				if(str[j]=='X'){
					if(k.first==-1){
						k.second=j;
						k.first=i;
					}
				}
				if(str[j]=='.'){
					o[cnt].second=j;
					o[cnt++].first=i;
				}
			}
		}
		if(k.first+k.second==0)printf("0\n");
		else if(cnt<2)printf("-1\n");
		else printf("%d\n",dijkstra(k,o[0],o[1]));
	}
	return 0;
}