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<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 50

enum DIR{
	North,
	East,
	South,
	West,
};

struct Data{
	Data(){
		row = col = 0;
	}
	Data(int arg_row,int arg_col){
		row = arg_row;
		col = arg_col;
	}
	void set(int arg_row,int arg_col){
		row = arg_row;
		col = arg_col;
	}
	int row,col;
};

struct Info{
	Info(Data arg_king,int arg_sum_cost,DIR arg_can_move_dir){
		king.row = arg_king.row;
		king.col = arg_king.col;
		sum_cost = arg_sum_cost;
		can_move_dir = arg_can_move_dir;
	}
	bool operator<(const struct Info &arg) const{
		return sum_cost > arg.sum_cost;
	}
	Data king;
	int sum_cost;
	DIR can_move_dir;
};

struct State{
	State(int arg_row,int arg_col,int arg_sum_cost){
		row = arg_row;
		col = arg_col;
		sum_cost = arg_sum_cost;
	}
	bool operator<(const struct State &arg) const{
		return sum_cost > arg.sum_cost;
	}
	int row,col,sum_cost;
};

int H,W;
int min_cost[NUM][NUM][4],memo[NUM][NUM][4][4],min_dist[NUM][NUM];
int diff_row[4] = {-1,0,1,0},diff_col[4] = {0,1,0,-1};
int diff_row_king[4] = {0,0,1,1},diff_col_king[4] = {0,1,0,1};
char base_map[NUM][NUM+1];
Data first_king,first_space[2];
DIR dir_array[4] = {North,East,South,West},rev_array[4] = {South,West,North,East};

bool rangeCheck(Data data){
	if(data.row >= 0 && data.row <= H-1 && data.col >= 0 && data.col <= W-1){
		return true;
	}else{
		return false;
	}
}

vector<Data> calc_space_loc(Data king,DIR dir){

	vector<Data> ret;

	switch(dir){

	case North:
		ret.push_back(Data(king.row-1,king.col));
		ret.push_back(Data(king.row-1,king.col+1));
		break;

	case East:
		ret.push_back(Data(king.row,king.col+2));
		ret.push_back(Data(king.row+1,king.col+2));
		break;

	case South:
		ret.push_back(Data(king.row+2,king.col));
		ret.push_back(Data(king.row+2,king.col+1));
		break;

	case West:
		ret.push_back(Data(king.row,king.col-1));
		ret.push_back(Data(king.row+1,king.col-1));
		break;
	}
	return ret;
}

int dijkstra(Data from, Data to){

	for(int row = 0; row < H; row++){
		for(int col = 0; col < W; col++){
			min_dist[row][col] = BIG_NUM;
		}
	}

	min_dist[from.row][from.col] = 0;

	priority_queue<State> Q;
	Q.push(State(from.row,from.col,0));

	int next_row,next_col;

	while(!Q.empty()){

		if(Q.top().row == to.row && Q.top().col == to.col){
			return Q.top().sum_cost;
		}

		for(int i = 0; i < 4; i++){
			next_row = Q.top().row+diff_row[i];
			next_col = Q.top().col+diff_col[i];

			if(rangeCheck(Data(next_row,next_col)) == false || base_map[next_row][next_col] == '*')continue;

			if(min_dist[next_row][next_col] > Q.top().sum_cost+1){
				min_dist[next_row][next_col] = Q.top().sum_cost+1;
				Q.push(State(next_row,next_col,Q.top().sum_cost+1));
			}
		}
		Q.pop();
	}

	return BIG_NUM;
}

int calc_move_cost(Data from_1,Data from_2,Data to_1,Data to_2,Data king){

	if(base_map[to_1.row][to_1.col] == '*' || base_map[to_2.row][to_2.col] =='*')return BIG_NUM;

	//王のいるマスを、障害マスにする
	for(int i = 0; i < 4; i++){
		base_map[king.row+diff_row_king[i]][king.col+diff_col_king[i]] = '*';
	}

	int cost_1,cost_2,cost_3,cost_4;
	int ret_1 = BIG_NUM,ret_2 = BIG_NUM;

	cost_1 = dijkstra(from_1,to_1);
	if(cost_1 != BIG_NUM){
		cost_2 = dijkstra(from_2,to_2);
		if(cost_2 != BIG_NUM){
			ret_1 = cost_1+cost_2;
		}
	}

	cost_3 = dijkstra(from_1,to_2);
	if(cost_3 != BIG_NUM){
		cost_4 = dijkstra(from_2,to_1);
		if(cost_4 != BIG_NUM){
			ret_2 = cost_3+cost_4;
		}
	}

	for(int i = 0; i < 4; i++){
		base_map[king.row+diff_row_king[i]][king.col+diff_col_king[i]] = 'X';
	}

	return min(ret_1,ret_2);
}

void func(){

	bool FLG = false;
	int first_space_index = 0;

	for(int row = 0; row < H; row++){
		scanf("%s",base_map[row]);

		if(!FLG){
			for(int col = 0; col < W; col++){
				if(base_map[row][col] == 'X'){
					first_king.set(row,col);
					FLG = true;
					break;
				}
			}
		}
		for(int col = 0; col < W; col++){
			if(base_map[row][col] == '.'){
				first_space[first_space_index++].set(row,col);
			}
		}
	}

	if(first_king.row == 0 && first_king.col == 0){
		printf("0\n");
		return;
	}

	for(int row = 0; row < H; row++){
		for(int col = 0; col < W; col++){
			for(int a = 0; a < 4; a++){
				min_cost[row][col][a] = BIG_NUM;
			}
		}
	}

	priority_queue<Info> Q;
	vector<Data> ret;
	int add_cost;

	for(int i = 0; i < 4; i++){

		ret = calc_space_loc(first_king,dir_array[i]);
		if(rangeCheck(ret[0]) == false || rangeCheck(ret[1]) == false)continue;

		add_cost = calc_move_cost(first_space[0],first_space[1],ret[0],ret[1],first_king);
		if(add_cost == BIG_NUM)continue;

		Q.push(Info(first_king,add_cost,dir_array[i]));
	}

	for(int row = 0; row < H; row++){
		for(int col = 0; col < W; col++){
			for(int a = 0; a < 4; a++){
				for(int b = 0; b < 4; b++){
					memo[row][col][a][b] = -1;
				}
			}
		}
	}

	Data next_king;
	DIR next_can_move_dir;
	vector<Data> from_space,to_space;

	while(!Q.empty()){

		if(Q.top().king.row == 0 && Q.top().king.col == 0){
			printf("%d\n",Q.top().sum_cost);
			return;
		}

		next_king.set(Q.top().king.row+diff_row[Q.top().can_move_dir],Q.top().king.col+diff_col[Q.top().can_move_dir]);
		next_can_move_dir = rev_array[Q.top().can_move_dir];

		if(min_cost[next_king.row][next_king.col][next_can_move_dir] > Q.top().sum_cost+1){
			min_cost[next_king.row][next_king.col][next_can_move_dir] = Q.top().sum_cost+1;
			Q.push(Info(next_king,Q.top().sum_cost+1,next_can_move_dir));
		}

		for(int i = 0; i < 4; i++){

			if(Q.top().can_move_dir == dir_array[i])continue;

			next_can_move_dir = dir_array[i];

			if(memo[Q.top().king.row][Q.top().king.col][Q.top().can_move_dir][next_can_move_dir] != -1){

				add_cost = memo[Q.top().king.row][Q.top().king.col][Q.top().can_move_dir][next_can_move_dir];

			}else{

				from_space = calc_space_loc(Q.top().king,Q.top().can_move_dir);
				to_space = calc_space_loc(Q.top().king,next_can_move_dir);
				if(rangeCheck(to_space[0]) == false || rangeCheck(to_space[1]) == false)continue;

				add_cost = calc_move_cost(from_space[0],from_space[1],to_space[0],to_space[1],Q.top().king);

				memo[Q.top().king.row][Q.top().king.col][Q.top().can_move_dir][next_can_move_dir] = add_cost;
			}

			if(add_cost == BIG_NUM)continue;

			if(min_cost[Q.top().king.row][Q.top().king.col][next_can_move_dir] > Q.top().sum_cost+add_cost){
				min_cost[Q.top().king.row][Q.top().king.col][next_can_move_dir] = Q.top().sum_cost+add_cost;
				Q.push(Info(Q.top().king,Q.top().sum_cost+add_cost,next_can_move_dir));
			}
		}

		Q.pop();
	}

	printf("-1\n");
}

int main(){

	while(true){
		scanf("%d %d",&H,&W);
		if(H == 0 && W == 0)break;

		func();
	}

	return 0;
}