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<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
//#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
#include<memory>
using namespace std;
//using namespace std::chrono;
typedef long long int llint;
typedef double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase

/*
cout<<fixed<<setprecision(20);
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint mod=110000007;//減らしてる
const llint big=2.19e17+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-7;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
/*
 0
3 1
 2
*/
//Sliding Block Puzzle
int h,w;
array<int,4>tomove(const array<array<char,64>,52>&mat,int ay,int ax,int by,int bx,int ky,int kx){
	//そっち方向に動くための距離を計算
	int i,j;
	int dist[52][52];
	for(i=0;i<=h+1;i++){
		for(j=0;j<=w+1;j++){
			dist[i][j]=mod;
		}
	}
	//axを計算
	queue<pair<int,int>>que;
	dist[ay][ax]=0;que.push(mp(ay,ax));
	while(que.size()){
		int y,x;tie(y,x)=que.front();que.pop();
		if(y<=0||x<=0||y>h||x>w){continue;}
		int t=dist[y][x];
		if(dist[y-1][x]==mod&&mat[y-1][x]=='o'){dist[y-1][x]=t+1;que.push(mp(y-1,x));}
		if(dist[y+1][x]==mod&&mat[y+1][x]=='o'){dist[y+1][x]=t+1;que.push(mp(y+1,x));}
		if(dist[y][x-1]==mod&&mat[y][x-1]=='o'){dist[y][x-1]=t+1;que.push(mp(y,x-1));}
		if(dist[y][x+1]==mod&&mat[y][x+1]=='o'){dist[y][x+1]=t+1;que.push(mp(y,x+1));}
	}
	int aaa[4][4];
	
	for(i=0;i<4;i++){
		for(j=0;j<4;j++){aaa[i][j]=dist[i+ky-1][j+kx-1];}
	}

	for(i=0;i<=h+1;i++){
		for(j=0;j<=w+1;j++){
			dist[i][j]=mod;
		}
	}
	//axを計算
	
	dist[by][bx]=0;que.push(mp(by,bx));
	while(que.size()){
		int y,x;tie(y,x)=que.front();que.pop();
		if(y<=0||x<=0||y>h||x>w){continue;}
		int t=dist[y][x];
		if(dist[y-1][x]==mod&&mat[y-1][x]=='o'){dist[y-1][x]=t+1;que.push(mp(y-1,x));}
		if(dist[y+1][x]==mod&&mat[y+1][x]=='o'){dist[y+1][x]=t+1;que.push(mp(y+1,x));}
		if(dist[y][x-1]==mod&&mat[y][x-1]=='o'){dist[y][x-1]=t+1;que.push(mp(y,x-1));}
		if(dist[y][x+1]==mod&&mat[y][x+1]=='o'){dist[y][x+1]=t+1;que.push(mp(y,x+1));}
	}
	array<int,4>ans;
	
	ans[0]=min(aaa[0][1]+dist[ky-1][kx+1],aaa[0][2]+dist[ky-1][kx]);
	ans[2]=min(aaa[3][1]+dist[ky+2][kx+1],aaa[3][2]+dist[ky+2][kx]);
	ans[3]=min(aaa[1][0]+dist[ky+1][kx-1],aaa[2][0]+dist[ky][kx-1]);
	ans[1]=min(aaa[1][3]+dist[ky+1][kx+2],aaa[2][3]+dist[ky][kx+2]);
	return ans;
}
bool solve(void){
	int i,j;cin>>h>>w;
	if(h==0){return false;}
	array<array<char,64>,52> mat;
	for(i=1;i<=h;i++){
		string str;
		cin>>str;
		for(j=1;j<=w;j++){mat[i][j]=str[j-1];}
		mat[i][0]='*';
		mat[i][w+1]='*';
	}
	for(j=0;j<=w+1;j++){mat[0][j]='*';mat[h+1][j]='*';}
	int sy,sx;
	int steAy=-1,steAx=-1,steBy,steBx;
	for(i=1;i<=h;i++){
		for(j=1;j<=w;j++){
			if(mat[i][j]=='X'){sy=i;sx=j;}
			if(mat[i][j]=='.'){
				mat[i][j]='o';
				if(steAy==-1){steAy=i;steAx=j;}
				else{steBy=i;steBx=j;}
			}
		}
	}
	sy--;sx--;
	if(sy==1&&sx==1){cout<<0<<endl;return true;}
	
	array<int,4> staugo;//スタートの動き方の表
	staugo=tomove(mat,steAy,steAx,steBy,steBx,sy,sx);
	mat[sy][sx]='o';
	mat[sy][sx+1]='o';
	mat[sy+1][sx]='o';
	mat[sy+1][sx+1]='o';
	
	array<array<int,4>,4> ugo[50][50];//動き方の遷移表
	
	for(i=1;i<h;i++){
		for(j=1;j<w;j++){
			if(mat[i][j]=='*'){continue;}
			if(mat[i][j+1]=='*'){continue;}
			if(mat[i+1][j]=='*'){continue;}
			if(mat[i+1][j+1]=='*'){continue;}
			mat[i][j]='X';
			mat[i][j+1]='X';
			mat[i+1][j]='X';
			mat[i+1][j+1]='X';
			ugo[i][j][0]=tomove(mat,i-1,j,i-1,j+1,i,j);
			ugo[i][j][1]=tomove(mat,i,j+2,i+1,j+2,i,j);
			ugo[i][j][2]=tomove(mat,i+2,j,i+2,j+1,i,j);
			ugo[i][j][3]=tomove(mat,i,j-1,i+1,j-1,i,j);
			mat[i][j]='o';
			mat[i][j+1]='o';
			mat[i+1][j]='o';
			mat[i+1][j+1]='o';
			
			
		}
	}
	
	array<int,4> dist[52][52];
	for(i=0;i<=h+1;i++){
		for(j=0;j<=w+1;j++){
			dist[i][j][0]=mod;
			dist[i][j][1]=mod;
			dist[i][j][2]=mod;
			dist[i][j][3]=mod;
		}
	}
	priority_queue<tuple<int,int,int,int>,vector<tuple<int,int,int,int>>,greater<tuple<int,int,int,int>>>que;
	dist[sy][sx]=staugo;
	que.push(mt(staugo[0],sy,sx,0));
	que.push(mt(staugo[1],sy,sx,1));
	que.push(mt(staugo[2],sy,sx,2));
	que.push(mt(staugo[3],sy,sx,3));
	int dy[4]={-1,0,1,0};
	int dx[4]={0,1,0,-1};
	while(que.size()){
		int t,y,x,d;tie(t,y,x,d)=que.top();que.pop();
		if(t>dist[y][x][d]){continue;}
		if(mineq(dist[y+dy[d]][x+dx[d]][d^2],t+1)){que.push(mt(t+1,y+dy[d],x+dx[d],d^2));}
		if(mineq(dist[y][x][0],t+ugo[y][x][d][0])){que.push(mt(dist[y][x][0],y,x,0));}
		if(mineq(dist[y][x][1],t+ugo[y][x][d][1])){que.push(mt(dist[y][x][1],y,x,1));}
		if(mineq(dist[y][x][2],t+ugo[y][x][d][2])){que.push(mt(dist[y][x][2],y,x,2));}
		if(mineq(dist[y][x][3],t+ugo[y][x][d][3])){que.push(mt(dist[y][x][3],y,x,3));}
	}
	
	
	int ans=mod;
	mineq(ans,dist[1][1][0]);
	mineq(ans,dist[1][1][1]);
	mineq(ans,dist[1][1][2]);
	mineq(ans,dist[1][1][3]);
	if(ans==mod){ans=-1;}
	cout<<ans<<endl;
	return true;
}
int main(void){
	cout<<fixed<<setprecision(20);
	cin.tie(0);
	ios::sync_with_stdio(false);
	while(solve()){}
	return 0;
}
/*
4 7
ooo*XXo
ooooXXo
oooo..o
ooooooo
*/