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 <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>
#include <cmath>
#include <sstream>
#include <cstring>

using namespace std;

template<typename T>
void filll_all(T& a, const T& v) { a = v; }
template<typename A, size_t N, typename T>
void filll_all(A(&a)[N], const T& v) { for (auto& aa : a) { filll_all(aa, v); } }

int H, W;
std::string mapmap[60];
const int64_t INF = 50505050;



bool is_in(int h, int w) {
	if (h < 0 || H <= h) {
		return false;
	}
	if (w < 0 || W <= w) {
		return false;
	}
	if (mapmap[h][w] == '*') {
		return false;
	}
	return true;
}

int64_t dist1[50][50];
int64_t dist2[50][50];
void distfunc(int h, int w, int starth, int startw, int64_t(&distarray)[50][50]) {

	int64_t(&dist)[50][50] = distarray;


	std::vector<std::pair<int, int>> que;
	que.push_back({ starth ,startw });
	filll_all(dist, INF);
	dist[starth][startw] = 0;

	int count = 0;
	while (!que.empty()) {
		++count;
		std::vector<std::pair<int, int>> next;


		for (auto& v : que) {

			const int diffh[4] = { -1,0,1,0 };
			const int diffw[4] = { 0,1,0,-1 };

			for (int i = 0; i < 4; ++i) {
				int nexth = v.first + diffh[i];
				int nextw = v.second + diffw[i];
				if (is_in(nexth, nextw) &&
					!((h == nexth && w == nextw) || (h + 1 == nexth && w == nextw) || (h == nexth && w + 1 == nextw) || (h + 1 == nexth && w + 1 == nextw))
					&& count < dist[nexth][nextw]) {
					dist[nexth][nextw] = count;
					next.push_back({ nexth, nextw });
				}

			}
		}

		que = std::move(next);
	}


}
int64_t dp[50][50][4];
bool visited[50][50][4];
int64_t func(int h, int w, int now, int v) {

	priority_queue<pair<pair<int, int>, pair<int, int> > > pq;

	pq.push({ {-v, now}, {h, w} });

	memset(visited, 0, sizeof(visited));

	while (pq.size()) {
		auto p = pq.top();
		pq.pop();

		int v = -p.first.first;
		int now = p.first.second;
		int h = p.second.first;
		int w = p.second.second;

		if (!is_in(h, w)) {
			return INF;
		}
		if (!is_in(h + 1, w)) {
			return INF;
		}
		if (!is_in(h, w + 1)) {
			return INF;
		}
		if (!is_in(h + 1, w + 1)) {
			return INF;
		}

		if (visited[h][w][now]) continue;
		visited[h][w][now] = true;

		if (h == 0 && w == 0) {
			return v;
		}

		const int diffh0[4] = { -1,0,1,0 };
		const int diffw0[4] = { 0,1,0,-1 };

		const int diffh2[4] = { -1,1,2,1 };
		const int diffw2[4] = { 1,2,1,-1 };
		if (!is_in(h + diffh2[now], w + diffw2[now])) {
			continue;
		}
		distfunc(h, w, h + diffh2[now], w + diffw2[now], dist2);

		const int diffh1[4] = { -1,0,2,0 };
		const int diffw1[4] = { 0,2,0,-1 };
		if (!is_in(h + diffh1[now], w + diffw1[now])) {
			continue;
		}
		distfunc(h, w, h + diffh1[now], w + diffw1[now], dist1);

		int dist11[4] = {};
		int dist12[4] = {};
		int dist21[4] = {};
		int dist22[4] = {};
		for (int next = 0; next < 4; next++) {
			int nexth1 = h + diffh1[next];
			int nextw1 = w + diffw1[next];
			if (!is_in(nexth1, nextw1)) {
				continue;
			}
			int nexth2 = h + diffh2[next];
			int nextw2 = w + diffw2[next];
			if (!is_in(nexth2, nextw2)) {
				continue;
			}

			dist11[next] = dist1[h + diffh1[next]][w + diffw1[next]];
			dist22[next] = dist2[h + diffh2[next]][w + diffw2[next]];
			dist21[next] = dist2[h + diffh1[next]][w + diffw1[next]];
			dist12[next] = dist1[h + diffh2[next]][w + diffw2[next]];
		}

		for (int next = 0; next < 4; next++) {
			int nexth1 = h + diffh1[next];
			int nextw1 = w + diffw1[next];
			if (!is_in(nexth1, nextw1)) {
				continue;
			}
			int nexth2 = h + diffh2[next];
			int nextw2 = w + diffw2[next];
			if (!is_in(nexth2, nextw2)) {
				continue;
			}

			int nextv = v + std::min(dist11[next] + dist22[next], dist21[next] + dist12[next]) + 1;
			if (nextv < INF) {
				pq.push({ {-nextv, next ^ 2}, {h + diffh0[next], w + diffw0[next]} });
			}
		}
	}

	return INF;
}

int main()
{
	while (true)
	{
		cin >> H >> W;
		if (H == 0 && W == 0) {
			break;
		}

		filll_all(dp, (int64_t)-1);
		for (size_t i = 0; i < H; i++)
		{
			cin >> mapmap[i];
		}

		int defh = -1, defw = -1;
		for (size_t i = 0; i < H; i++)
		{
			for (size_t j = 0; j < W; j++)
			{
				if (mapmap[i][j] == 'X') {
					defh = i;
					defw = j;
					goto ROOPROOPROOP;
				}
			}
		}
	ROOPROOPROOP:;
		if (defh == 0 && defw == 0) {
			cout << "0\n";
			continue;
		}
		int count = 0;
		for (size_t i = 0; i < H; i++)
		{
			for (size_t j = 0; j < W; j++)
			{
				if (mapmap[i][j] == '.') {
					if (count == 0) {
						distfunc(defh, defw, i, j, dist1);
						++count;
					}
					else {
						distfunc(defh, defw, i, j, dist2);
					}
				}
			}
		}


		const int diffh2[4] = { -1,1,2,1 };
		const int diffw2[4] = { 1,2,1,-1 };
		const int diffh1[4] = { -1,0,2,0 };
		const int diffw1[4] = { 0,2,0,-1 };

		auto h = defh;
		auto w = defw;
		int64_t res = INF;
		int dist11[4] = {};
		int dist12[4] = {};
		int dist21[4] = {};
		int dist22[4] = {};
		for (int next = 0; next < 4; next++)
		{
			int nexth1 = h + diffh1[next];
			int nextw1 = w + diffw1[next];
			if (!is_in(nexth1, nextw1)) {
				continue;
			}
			int nexth2 = h + diffh2[next];
			int nextw2 = w + diffw2[next];
			if (!is_in(nexth2, nextw2)) {
				continue;
			}

			dist11[next] = dist1[h + diffh1[next]][w + diffw1[next]];
			dist22[next] = dist2[h + diffh2[next]][w + diffw2[next]];
			dist21[next] = dist2[h + diffh1[next]][w + diffw1[next]];
			dist12[next] = dist1[h + diffh2[next]][w + diffw2[next]];
		}

		for (int next = 0; next < 4; next++) {
			int nexth1 = h + diffh1[next];
			int nextw1 = w + diffw1[next];
			if (!is_in(nexth1, nextw1)) {
				continue;
			}
			int nexth2 = h + diffh2[next];
			int nextw2 = w + diffw2[next];
			if (!is_in(nexth2, nextw2)) {
				continue;
			}

			int v = std::min(dist11[next] + dist22[next], dist21[next] + dist12[next]);

			res = min(res, func(h, w, next, v));
		}

		if (res == INF) {
			cout << "-1\n";
		}
		else {
			cout << res << '\n';
		}
	}
}