eolymp
bolt
Try our new interface for solving problems
Problems

Terminator

Terminator

Time limit 1 second
Memory limit 64 MiB

Two players play a board game. The game field represents a square maze, 8×8 cells. Some cells are walls. One player controls the chip-terminated, and the second - chip-fugitive. Players take turns, moves can not miss (guaranteed that the course is always possible). In one move, the player may move his token in any of the free cells adjacent to the original horizontally, vertically, or diagonally (ie, move the king). The Terminator, in addition, can shoot the fugitive missiles. The shot goes in a straight line in any direction horizontally, vertically or diagonally. If the fugitive is on the line terminator, and the shot is not covered walls, the termination shall immediately make a shot (no matter whose turn), and fugitive loses. The initial position chips set. The first move is made ​​a fugitive. He wins if he does move to the eighth row outside the playing field, as the rest of a field surrounded by walls.

Question of the problem: whether the fugitive to win the game at the optimum of both parties?

Input data

The input file is given the playing field. Free cell denotes the number 0, and the cell-wall - the number 1. The cell in which the fugitive is designated numeral 2, a cell with a terminator - the number 3.

Output data

The output file output number 1, if the fugitive wins and -1 - otherwise.

Examples

Input example #1
01000000
10100000
31100000
00020000
00000000
00000000
00000000
00000000
Output example #1
-1