#include<iostream>
#include<map>
#include<algorithm>
#include<queue>

#define rep(i,n) for(int i=0;i<n;i++)
#define fs first
#define sc second
using namespace std;
typedef pair<int,int> P;
typedef pair<P,int> P2;

const int dy[] = {-1,-1,0,1,1,1,0,-1}, dx[] = {0,1,1,1,0,-1,-1,-1};
int sy,sx;
string b[20];
map<P,int> stone;

string bin(int x){
  string res;
  for(int i=0;i<20;i++){
    if(x&1)res += "1";
    else res += "0";
    x/=2;
  }
  return res;
}

int main(){
  for(int i=0;i<19;i++)cin >> b[i];

  int cnt = 0;
  for(int i=0;i<19;i++){
    for(int j=0;j<15;j++){
      if(b[i][j] == 'O'){sy = i; sx = j;}
      if(b[i][j] == 'X'){
	stone[P(i,j)] = cnt++;
      }
    }
  }

  P2 cur = P2(P(sy,sx),0);
  map<P2,int> d;
  d[cur] = 0;
  queue<P2> q;
  q.push(cur);

  int res = -1;
  while(q.size()){
    cur = q.front(); q.pop();
    int state = cur.sc;

    for(int i=0;i<8;i++){
      int ny = cur.fs.fs+dy[i], nx = cur.fs.sc+dx[i];
      int nstate = state;

      if(ny<0 || nx<0 || ny>=19 || nx>=15)continue;
      while(b[ny][nx] == 'X'){
	int id = stone[P(ny,nx)];

	if((nstate>>id)&1)break;

	nstate |= 1<<id;
        ny = ny+dy[i], nx = nx+dx[i];

	if(ny<0 || nx<0 || ny>=19 || nx>=15)break;
      }
      if(ny==cur.fs.fs+dy[i] && nx==cur.fs.sc+dx[i])continue;

      if(ny>=19){
	res = d[cur]+1;
	goto END;
      }
      
      if(ny<0 || nx<0 || nx>=15)continue;
      if(ny>=18){
	res = d[cur]+1;
	goto END;
      }

      P2 nxt = P2(P(ny,nx),nstate);
      if(d.find(nxt) == d.end()){
	q.push(nxt);
	d[nxt] = d[cur]+1;
      }
    }
  }
 END: cout << res << endl;
}
### Prompt

In CPP, your task is to solve the following problem:

Ikta, who hates to lose, has recently been enthusiastic about playing games using the Go board. However, neither Go nor Gomoku can beat my friends at all, so I decided to give a special training to the lesser-known game Phutball.

This game is a difficult game, so I decided to give special training so that I could win my turn and decide if I could finish it.

The conditions for winning the game are as follows.

* Shiraishi cannot jump to the place where Kuroishi is placed.
* Use the 19 x 15 part in the center of the board.
* The board for which you want to judge the victory conditions is given with one white stone and several black stones.
* The goal point is the lower end of the board or the lower side. (See the figure below.)
* If you bring Shiraishi to the goal point, you will win.
* To win, do the following:
* Shiraishi can make one or more jumps.
* Jumping can be done by jumping over any of the eight directions (up, down, left, right, diagonally above, diagonally below) adjacent to Shiraishi.
* It is not possible to jump in a direction where Kuroishi is not adjacent.
* The jumped Kuroishi is removed from the board for each jump.
* After jumping, Shiraishi must be at the goal point or on the game board.
* Even if there are two or more Kuroishi in a row, you can jump just across them.
* Shiraishi cannot jump to the place where Kuroishi is placed. (Kuroishi that is continuous in the direction of jump must be jumped over.)

<image>



It is possible to jump to the places marked with circles in the figure, all of which are goal points, but since the places marked with crosses are neither the goal points nor the inside of the board, it is not possible to jump.

Your job is to help Ikta write a program to determine if you can reach the goal and to find the minimum number of jumps to reach the goal.



Input

A 19 x 15 board composed of .OX is given in 19 lines. Each line always consists of 15 characters, and each character represents the following:

* "." Represents a blank.
* "O" stands for Shiraishi.
* "X" stands for Kuroishi.



Constraints

* The number of black stones is 20 or less.
* There is always only one Shiraishi.
* The state that has already been reached will not be entered.

Output

Goal If possible, output the shortest effort on one line. If it is impossible to reach the goal, output -1.

Examples

Input

...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
......O........
......X........


Output

1


Input

...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
......O........
...............


Output

-1


Input

...............
...............
...............
...............
...............
...............
...............
...............
...........O...
............X..
.............X.
.............X.
.............X.
...............
..............X
.........X.....
.............X.
......X....X..X
.....X.X.XX.X..


Output

6


Input

...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
.....XX........
.....XXXO......
......X........


Output

4

### Response

```cpp
#include<iostream>
#include<map>
#include<algorithm>
#include<queue>

#define rep(i,n) for(int i=0;i<n;i++)
#define fs first
#define sc second
using namespace std;
typedef pair<int,int> P;
typedef pair<P,int> P2;

const int dy[] = {-1,-1,0,1,1,1,0,-1}, dx[] = {0,1,1,1,0,-1,-1,-1};
int sy,sx;
string b[20];
map<P,int> stone;

string bin(int x){
  string res;
  for(int i=0;i<20;i++){
    if(x&1)res += "1";
    else res += "0";
    x/=2;
  }
  return res;
}

int main(){
  for(int i=0;i<19;i++)cin >> b[i];

  int cnt = 0;
  for(int i=0;i<19;i++){
    for(int j=0;j<15;j++){
      if(b[i][j] == 'O'){sy = i; sx = j;}
      if(b[i][j] == 'X'){
	stone[P(i,j)] = cnt++;
      }
    }
  }

  P2 cur = P2(P(sy,sx),0);
  map<P2,int> d;
  d[cur] = 0;
  queue<P2> q;
  q.push(cur);

  int res = -1;
  while(q.size()){
    cur = q.front(); q.pop();
    int state = cur.sc;

    for(int i=0;i<8;i++){
      int ny = cur.fs.fs+dy[i], nx = cur.fs.sc+dx[i];
      int nstate = state;

      if(ny<0 || nx<0 || ny>=19 || nx>=15)continue;
      while(b[ny][nx] == 'X'){
	int id = stone[P(ny,nx)];

	if((nstate>>id)&1)break;

	nstate |= 1<<id;
        ny = ny+dy[i], nx = nx+dx[i];

	if(ny<0 || nx<0 || ny>=19 || nx>=15)break;
      }
      if(ny==cur.fs.fs+dy[i] && nx==cur.fs.sc+dx[i])continue;

      if(ny>=19){
	res = d[cur]+1;
	goto END;
      }
      
      if(ny<0 || nx<0 || nx>=15)continue;
      if(ny>=18){
	res = d[cur]+1;
	goto END;
      }

      P2 nxt = P2(P(ny,nx),nstate);
      if(d.find(nxt) == d.end()){
	q.push(nxt);
	d[nxt] = d[cur]+1;
      }
    }
  }
 END: cout << res << endl;
}
```