Seven Seas

Time Limit: 5 Seconds    Memory Limit: 32768 KB

Seven Seas is one of my favourite games of Fantasy Games series. In the game you set sail with a white galleon for an ocean, and encounter a lot of pirate ships. You have to control your galleon to eliminate all the pirate ships. You can destroy them with your cannons, or lure them into collisions with island reefs and each other.

Let's consider a simplified game mode following.

Scene and Roles

  • The area of ocean the game holds is considered as 11 * 11 squares. Some squares may be islands, and others are seas.
  • Your white galleon is located on one square and faces to east (right) initially.
  • Some pirate ships are located on other squares initially.
  • There are not any shipwreck initially.

Movements

  • Each turn your galleon can move into one of the 8 squares surrounding it, unless the square is blocked by an island, shipwreck or pirate ship (of course you can't get outside the 11 * 11 area), then the galleon will face to the corresponding direction (north, north-east, east, south-east, south, south-west, west or north-west). You can also choose to stay there and fire your galleon's cannons either (once you stay, you will fire anyway).
  • After your turn, each pirate ship will move into one of the 8 squares surround it. They will choose the direction that leads them to get the closest to you (no matter what is on the front).
  • If a pirate ship collides with an island or a shipwreck, it will be destroyed.
  • If two or more pirate ships move into the same square, they will collide with each other and be destroyed, leaving a shipwreck on the square.

Attacking

  • You will fire your cannons when you choose to stay for your turn. You'll always fire a broadside to the left and right of your galleon (e.g. if your galleon faces to north-east, you'll fire to both the north-west and south-east). Your cannons have a range of 3 squares unless blocked by an island.
  • Islands can block your cannons, so you can't attack a pirate ship farther than an island on a certain side.
  • Shipwrecks can be fired over with your cannons.
  • Pirate ships can also block your cannons, so you can only attack the nearest pirate ship (with a distance no more than 3) on a certain side.
  • If a cannon to a certain side is blocked by an island or no pirate ships are in it's attack range, the firing is useless.
  • The pirate ships being attacked will be destroyed and leave a shipwreck on the square.

Goal

  • Once your galleon and a pirate ship are on the same square, you are caught.
  • Your objective is to eliminate all the pirate ships without getting caught .

Now is your task. What is the minimum number of turns you need to finish the game?

Input

Input contains multiple test cases. Each test case has 11 lines, each line consists of 11 characters. The characters may be '.', '*', 'O', 'X', which specify a sea, an island, your white galleon or a pirate ship respectively. It is possible that there are no pirate ships on ocean. Every test case will be followed by a blank line.

Output

There is one line for each test case, which is the minimum number of turns you need to finish the game. If you can't eliminate all the pirate ships without getting caught, just output -1.

Sample Input

...........
......X....
.....X.....
.X.........
...........
.....O..X..
......*....
...........
.....X.....
...........
...........

XXXXXXXXXXX
X.........X
X.........X
X.........X
X.........X
X....O....X
X.........X
X.........X
X.........X
X.........X
XXXXXXXXXXX

Sample Output

3
5
Submit

Source: Online Contest of Fantastic Game