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<vector>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cassert>
#include<climits>
#include<iomanip>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define inf (1<<28)
#define MAX 51
using namespace std;
int h,w;
string G[MAX];
int mincost[MAX*MAX][4][4];
int dx[] = {+0,+1,+0,-1};//&#9757;↑→↓←
int dy[] = {-1,+0,+1,+0};
int kdx[] = {0,1,1,0};
int kdy[] = {0,0,1,1};

/*

o <- od 
2 <- d2
   o2
  2KKo
  oKK2
   2o    

 */
int dx2[] = {+1,+0,-1,+0};
int dy2[] = {+0,+1,+0,-1};

int odx[] = {+0,+2,+1,-1};
int ody[] = {-1,+0,+2,+1};

struct P
{
  int x,y;
  P(int x=-1,int y=-1):x(x),y(y){}
};

struct Pox
{
  P p;
  int cost;
  Pox(P p = P(),int cost=-1):p(p),cost(cost){}
  bool operator < (const Pox &a)const
  {
    return cost > a.cost;
  }
};

struct Pess
{
  P p;
  int cost;
  int dir;
  Pess(P p = P(),int cost=-1,int dir=-1):p(p),cost(cost),dir(dir){}
  bool operator < (const Pess &a)const
  {
    return cost > a.cost;
  }
};

inline
int getIndex(P p){ return p.x+p.y*w; }

int open_mincost[MAX*MAX];

void open_the_door(P pxl,P king)//do not move the king before using this function
{

  priority_queue<Pox> Q;
  Q.push(Pox(pxl,0));
  bool used[MAX*MAX];
  bool in_king[MAX*MAX];
  rep(i,MAX*MAX)open_mincost[i] = inf,used[i] = false,in_king[i] = false;
  open_mincost[getIndex(pxl)] = 0;
  int cnt = 0;
  rep(i,4)
    {
      int kx = king.x + kdx[i];
      int ky = king.y + kdy[i];

      if(!(0 <= kx && kx < w && 0 <= ky && ky < h))
	{
	  //cout << "XXXXX error XXXXX" << endl;
	  //cout << kx << "," << ky << " are out of the range" << endl;
	  assert(false);
	}
      //cout << "king : " << kx << "," << ky << " = " << getIndex(P(kx,ky))<< endl;
      in_king[getIndex(P(kx,ky))] = true;
    }

  rep(i,4)
    {
      int x1 = king.x + odx[i];
      int y1 = king.y + ody[i];
      if(0 <= x1 && x1 < w && 0 <= y1 && y1 < h && G[y1][x1] != '*')
	{	
	  //cout << "add " << x1 << "," << y1 << endl;
	  used[getIndex(P(x1,y1))] = true;
	  cnt++; 
	}
      int x2 = x1 + dx2[i];
      int y2 = y1 + dy2[i];
      if(0 <= x2 && x2 < w && 0 <= y2 && y2 < h && G[y2][x2] != '*')
	{
	  //cout << "add " << x2 << "," << y2 << endl;
	  used[getIndex(P(x2,y2))] = true;
	  cnt++; 
	}

    }
  //cout << "cnt = " << cnt << endl;
  while(!Q.empty())
    {
      Pox pox = Q.top(); Q.pop();
      if(used[getIndex(pox.p)])
	{
	  //cout <<"here "<< pox.p.x << "," << pox.p.y << endl;
	  used[getIndex(pox.p)] = false;
	  cnt--;
	}
      if(cnt <= 0)
	return;

      rep(i,4)
	{
	  int nx = pox.p.x + dx[i];
	  int ny = pox.p.y + dy[i];
	  //cout << "from" << pox.p.x << "," << pox.p.y << " want to go to " << nx << "," << ny << endl;
	  if(!(0 <= nx && nx < w && 0 <= ny && ny < h))continue;
	  //cout << "---1" << endl;
	  if(G[ny][nx] == '*')continue;
	  //cout << "---3 " << nx << "," << ny << " " << in_king[getIndex(P(nx,ny))] << endl;	    
	  if(in_king[getIndex(P(nx,ny))])continue;
	  //cout << "---4" << endl;
	  //cout << "now : " << open_mincost[getIndex(P(nx,ny))] << " >? "<< pox.cost+1 << endl;
	  if(open_mincost[getIndex(P(nx,ny))] > pox.cost+1)
	    {
	      //cout << "goto " << nx << "," << ny  << " : cost = " << pox.cost+1<< endl;
	      //assert(!(nx == 3 && ny == 2));
	      open_mincost[getIndex(P(nx,ny))] = pox.cost+1;
	      Q.push(Pox(P(nx,ny),pox.cost+1));
	    }
	}
    }
}

void init_mincost()
{
  int temp[4][2];
  rep(i,MAX*MAX)rep(j,4)rep(k,4)mincost[i][j][k] = inf;

  rep(i,h)
    {
      if(i+1 >= h)continue;
      rep(j,w)
	{
	  if(G[i][j] == '*')continue;
	  if(j+1 >= w)continue;
	  rep(k,4)
	    {
	      int nx = j + odx[k];
	      int ny = i + ody[k];
	      if(!(0 <= nx && nx < w && 0 <= ny && ny < h))continue;
	      if(G[ny][nx] == '*')continue;

	      int mx = nx + dx2[k];
	      int my = ny + dy2[k];
	      if(!(0 <= mx && mx < w && 0 <= my && my < h))continue;
	      if(G[my][mx] == '*')continue;

	      open_the_door(P(nx,ny),P(j,i));//calculate the minimum cost from P(nx,ny) to all cells
	      rep(l,4)
		{//store the information about the minimum cost from P(nx,ny)
		  int x1 = j + odx[l];
		  int y1 = i + ody[l];
		  if(!(0 <= x1 && x1 < w && 0 <= y1 && y1 < h) || G[y1][x1] == '*')
		    {
		      temp[l][0] = temp[l][1] = inf;
		      continue;
		    }
		  int x2 = x1 + dx2[l];
		  int y2 = y1 + dy2[l];
		  if(!(0 <= x2 && x2 < w && 0 <= y2 && y2 < h) || G[y2][x2] == '*')
		    {
		      temp[l][0] = temp[l][1] = inf;
		      continue;
		    }
		  temp[l][0] = open_mincost[getIndex(P(x1,y1))];
		  temp[l][1] = open_mincost[getIndex(P(x2,y2))];

		}
	      /*
		  if(j == 4 && i == 2 && k == 2)
		    {
		      cout << "origine!" << endl;
		      cout << temp[3][0] << " " << temp[3][1] << endl;
		    }
	      */
	      open_the_door(P(mx,my),P(j,i));//caluclate the minimum cost from P(mx,my) to all cells

	      rep(l,4)
		{
		  int x1 = j + odx[l];
		  int y1 = i + ody[l];
		  if(!(0 <= x1 && x1 < w && 0 <= y1 && y1 < h) || G[y1][x1] == '*')
		    {
		      continue;
		    }
		  int x2 = x1 + dx2[l];
		  int y2 = y1 + dy2[l];
		  if(!(0 <= x2 && x2 < w && 0 <= y2 && y2 < h) || G[y2][x2] == '*')
		    {
		      continue;
		    }
		  mincost[getIndex(P(j,i))][k][l] = min(temp[l][0]+open_mincost[getIndex(P(x2,y2))],
							temp[l][1]+open_mincost[getIndex(P(x1,y1))]);


		  if(k == l)
		    {
		      assert(mincost[getIndex(P(j,i))][k][l] == 0);
		    }
		}

	      /*
		  if(j == 4 && i == 2 && k == 2)
		    {
		      cout << "habeii!" << endl;
		      cout << mincost[getIndex(P(4,2))][2][3] << endl;
		    }
	      */
	    }
	}
    }

}

/* collisionする場合ってありえる？
->そもそも関係ない気がする！！！
XXXXXXX
      X
XXXXX↓X
   →collision!!!
XXXXX
XXXXXXXXXXXX.................................................
.....XXXXXXX......................................
.XXX.....XXXX.....................................
...XXXXX....X.....................................
KK.....X.XX.X.....................................
KKXXXX...X........................................
..X..XXXXX........................................
.....XXXXX........................................
..................................................
 */



int King_Of_The_King[4];//&#9757;上、右、下、左

bool check(int x,int y)
{
  //cout << "isok? " << x << "," << y << " "; 
  rep(i,4)
    {
      int kx = x + kdx[i];
      int ky = y + kdy[i];
      if(!(0 <= kx && kx < w && 0 <= ky && ky < h))
	{
	  //cout << "NO!" << endl;
	  return false;
	}
      if(G[ky][kx] == '*')
	{
	  //cout << "NO!!" << endl;
	  return false;
	}
    }
  //cout << " oK!" << endl;
  return true;
}

int costc[MAX*MAX][4];
void dijkstra(P king)
{
  priority_queue<Pess> Q;
  rep(i,4)
    Q.push(Pess(king,King_Of_The_King[i],i));

  rep(i,MAX*MAX)rep(j,4)costc[i][j] = inf;
  rep(i,4)costc[getIndex(king)][i] = King_Of_The_King[i];

  while(!Q.empty())
    {
      Pess pess = Q.top(); Q.pop();
      //cout << "------------- " << pess.p.x << "," << pess.p.y << endl;
      if(pess.p.x == 0 && pess.p.y == 0)
	{
	  cout << pess.cost << endl;
	  return;
	}
      rep(i,4)
	{
	  int nx = pess.p.x + dx[i];
	  int ny = pess.p.y + dy[i];
	  if(!check(nx,ny))continue;
	  //cout << "to " << nx << "," << ny << "  " << costc[getIndex(P(nx,ny))][(i+2)%2] << " > " << pess.cost << "+" << mincost[getIndex(pess.p)][pess.dir][i]+1 << " mincost["<<pess.p.x << ","<< pess.p.y<<"]["<<pess.dir<<"]["<<i<<"]"<< endl;
	  if(costc[getIndex(P(nx,ny))][(i+2)%2] > pess.cost+mincost[getIndex(pess.p)][pess.dir][i]+1)
	    {
	      //cout << "from " << pess.p.x << "," << pess.p.y << " to " << nx << "," << ny << endl;
	      costc[getIndex(P(nx,ny))][(i+2)%2] = pess.cost+mincost[getIndex(pess.p)][pess.dir][i]+1;
	      Q.push(Pess(P(nx,ny),pess.cost+mincost[getIndex(pess.p)][pess.dir][i]+1,(i+2)%4));	    
	    }
	}
    }
  cout << -1 << endl;
}

//its time to play the game
void move_open_to_the_side_of_King(P o1,P o2,P king)
{
  int temp[4][2];

  open_the_door(o1,king);
  rep(i,4)
    {
      int x1 = king.x + odx[i];
      int y1 = king.y + ody[i];
      if(!(0 <= x1 && x1 < w && 0 <= y1 && y1 < h) || G[y1][x1] == '*')
	{
	  //temp[i][0] = temp[i][1] = inf;
	  temp[i][0] = temp[i][1] = 0;
	  continue;
	}
      int x2 = x1 + dx2[i];
      int y2 = y1 + dy2[i];
      if(!(0 <= x2 && x2 < w && 0 <= y2 && y2 < h) || G[y2][x2] == '*')
	{
	  //temp[i][0] = temp[i][1] = inf;
	  temp[i][0] = temp[i][1] = 0;
	  continue;
	}
      temp[i][0] = open_mincost[getIndex(P(x1,y1))];
      temp[i][1] = open_mincost[getIndex(P(x2,y2))];
    }

  open_the_door(o2,king);
 rep(i,4)
    {
      int x1 = king.x + odx[i];
      int y1 = king.y + ody[i];
      if(!(0 <= x1 && x1 < w && 0 <= y1 && y1 < h) || G[y1][x1] == '*')
	{
	  //King_Of_The_King[i] = inf;
	  King_Of_The_King[i] = 0;
	  continue;
	}
      int x2 = x1 + dx2[i];
      int y2 = y1 + dy2[i];
      if(!(0 <= x2 && x2 < w && 0 <= y2 && y2 < h) || G[y2][x2] == '*')
	{
	  //King_Of_The_King[i] = inf;
	  King_Of_The_King[i] = 0;
	  continue;
	}

      //cout << temp[i][0] << "," << temp[i][1] << " " << open_mincost[getIndex(P(x2,y2))] << "," << open_mincost[getIndex(P(x1,y1))] << endl;
      King_Of_The_King[i] = min(temp[i][0]+open_mincost[getIndex(P(x2,y2))],
				temp[i][1]+open_mincost[getIndex(P(x1,y1))]);
    }

}




int main()
{
  //clock_t st,ed;
  //st = clock();
  while(cin >> h >> w,h|w)
    {

      vector<P> open;
      P king;

      rep(i,h)
	{
	  cin >> G[i];
	  rep(j,w)
	    {
	      if(G[i][j]  == '.')
		open.push_back(P(j,i));
	      
	      if(G[i][j] == 'X' && king.x == -1 && king.y == -1)
		king = P(j,i);
	    }
	}

      if(king.x == 0 && king.y == 0)
	{
	  cout << 0 << endl;
	  continue;
	}

      init_mincost();
      move_open_to_the_side_of_King(open[0],open[1],king);
      dijkstra(king);
      //move_open_to_the_side_of_King(open[0],open[1],king);
      //cout << King_Of_The_King[0] << endl;
      //cout << King_Of_The_King[1] << endl;
      //cout << King_Of_The_King[2] << endl;
      //cout << King_Of_The_King[3] << endl;

      //open_the_door(P(4,4),P(4,2));
      
      //cout << open_mincost[getIndex(P(3,2))] << endl;
      //cout << open_mincost[getIndex(P(3,3))] << endl;
      /*
      init_mincost();
      int cnt = 1;
      rep(i,h)
      {
      rep(j,w)
      {
	//cout << "from " << j << " " << i << endl;
      rep(k,4)
      {
      rep(l,4)
      {
	if(cnt == 113)
	  {
	    cout << i << " " << j << " " << k << " " << l << endl;
	  }
	cnt++;
	if(mincost[j+i*w][k][l] >= inf)cout << 0 << endl;
	else cout << mincost[j+i*w][k][l]+1 << endl;
      }
      }
      }
      }
      */
      //cout << mincost[getIndex(P(3,3))][0][2] << endl;
      
    }
  //ed = clock();
  //cout << setiosflags(ios::fixed) << setprecision(10) << (double)(ed-st)/CLOCKS_PER_SEC << endl;
  return 0;
}