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<queue>
#include<cstdio>
#include<cstring>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

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

struct point{
	int x,y;
	bool operator<(const point &p)const{ return true; } // dummy
};

int h,w;
char B[52][53];

vector<point> get_space_pos(point king,int dir){
	vector<point> res;
	int t=king.y,l=king.x,b=king.y+1,r=king.x+1;
	if(dir==0) res.push_back((point){r+1,t}), res.push_back((point){r+1,b});
	if(dir==1) res.push_back((point){l,t-1}), res.push_back((point){r,t-1});
	if(dir==2) res.push_back((point){l-1,t}), res.push_back((point){l-1,b});
	if(dir==3) res.push_back((point){l,b+1}), res.push_back((point){r,b+1});
	return res;
}

int bfs(const point &s,const point &g){
	if(B[s.y][s.x]=='*' || B[g.y][g.x]=='*') return INF;

	static int d[52][52];
	rep(i,h) rep(j,w) d[i][j]=INF;
	d[s.y][s.x]=0;

	int head=0,tail=0;
	static int Q[52*52]; Q[tail++]=s.y*w+s.x;
	while(head<tail){
		int y=Q[head]/w,x=Q[head]%w; head++;

		if(y==g.y && x==g.x) return d[y][x];

		rep(k,4){
			int yy=y+dy[k],xx=x+dx[k];
			if(B[yy][xx]!='*' && d[yy][xx]==INF){
				d[yy][xx]=d[y][x]+1;
				Q[tail++]=yy*w+xx;
			}
		}
	}

	return INF;
}

// 2 つの space が p0, p1 にあるとき, これらを p2, p3 に移動させるための最小コスト
int calc_space_moving_cost(const point &p0,const point &p1,const point &p2,const point &p3,const point king){

	static char tmp[52][53];
	memcpy(tmp,B,sizeof B);

	// king のマスを障害物にする
	B[king.y+0][king.x+0]='*';
	B[king.y+0][king.x+1]='*';
	B[king.y+1][king.x+0]='*';
	B[king.y+1][king.x+1]='*';

	int d02=bfs(p0,p2);
	int d03=bfs(p0,p3);
	int d12=bfs(p1,p2);
	int d13=bfs(p1,p3);
// printf("  d02 = %d\n",d02);
// printf("  d03 = %d\n",d03);
// printf("  d12 = %d\n",d12);
// printf("  d13 = %d\n",d13);

	memcpy(B,tmp,sizeof B);

	return min(d02+d13,d03+d12);
}

int main(){
	while(scanf("%d%d",&h,&w),h){
		rep(j,w+2) B[0][j]='*';
		rep(i,h){
			B[i+1][0]='*';
			scanf("%s",B[i+1]+1);
			B[i+1][w+1]='*';
		}
		rep(j,w+2) B[h+1][j]='*';
		rep(i,h+2) B[i][w+2]='\0';
		h+=2;
		w+=2;

		// king と space の初期位置
		point king0={-1,-1};
		vector<point> space0;
		rep(i,h) rep(j,w) {
			if(B[i][j]=='X' && king0.x==-1) king0=(point){j,i};
			if(B[i][j]=='.') space0.push_back((point){j,i});
		}

		if(king0.y==1 && king0.x==1){ puts("0"); continue; }

		static int space_cost[52][52][4][4];
		memset(space_cost,-1,sizeof space_cost);

		// Dijkstra
		static int d[52][52][4];
		rep(i,h) rep(j,w) rep(k,4) d[i][j][k]=INF;

		int ans=-1;
		priority_queue< pair<int,pair<point,int> > > Q; // <-cost,<king の位置,space が king の四方どの向きについているか>>
		rep(dir,4){
			vector<point> space=get_space_pos(king0,dir);
			int cost=calc_space_moving_cost(space0[0],space0[1],space[0],space[1],king0);
			if(cost<INF){
				d[king0.y][king0.x][dir]=cost;
				Q.push(make_pair(-cost,make_pair(king0,dir)));
			}
		}
		while(!Q.empty()){
			int d_now=-Q.top().first,dir=Q.top().second.second;
			point king=Q.top().second.first; Q.pop();

			if(d[king.y][king.x][dir]<d_now) continue;

			if(king.y==1 && king.x==1){ ans=d_now; break; }

			// king を動かす
			point king2={king.x+dx[dir],king.y+dy[dir]};
			int dir2=(dir+2)%4;
			if(d[king2.y][king2.x][dir2]>d_now+1){
				d[king2.y][king2.x][dir2]=d_now+1;
				Q.push(make_pair(-(d_now+1),make_pair(king2,dir2)));
			}

			// space を動かす
			vector<point> space=get_space_pos(king,dir);
			for(dir2=0;dir2<4;dir2++) if(dir2!=dir) {
				vector<point> space2=get_space_pos(king,dir2);

				int &cost=space_cost[king.y][king.x][dir][dir2];  // 毎回計算しなおすと遅いので一回計算したものはメモする
				if(cost==-1){
					cost=calc_space_moving_cost(space[0],space[1],space2[0],space2[1],king);
				}

				if(d[king.y][king.x][dir2]>d_now+cost){
					d[king.y][king.x][dir2]=d_now+cost;
					Q.push(make_pair(-(d_now+cost),make_pair(king,dir2)));
				}
			}
		}

		printf("%d\n",ans);
	}

	return 0;
}