Determinant#762

Determinant

1 second

64 megabytes

Hard

The game Determinant is played by two players on a $3 \times 3$ 3 \times 3 grid. Players take turns writing a single digit into empty cells, ensuring that each digit is used only once.

For example, in a given position, the current player can choose from the digits $1$ , $2$ , $4$ , $5$ , $6$ , $7$ , $8$ to place in any empty cell.

Once all cells are filled, the determinant $D$ of the grid is calculated using the formula:

D = A_{11} A_{22} A_{33} + A_{12} A_{23} A_{31} + A_{13} A_{21} A_{32} - A_{11} A_{23} A_{32} - A_{12} A_{21} A_{33} - A_{13} A_{22} A_{31}

D = A_{11}A_{22}A_{33} + A_{12}A_{23}A_{31} + A_{13}A_{21}A_{32} - A_{11}A_{23}A_{32} - A_{12}A_{21}A_{33} - A_{13}A_{22}A_{31}

If the determinant is greater than zero ( $D > 0$ D > 0), the player who started the game wins. If the determinant is less than zero ( $D < 0$ D < 0), the player who went second wins. If the determinant equals zero ( $D = 0$ D = 0), the game is a draw.

Your task is to determine the outcome of the game from the given position, assuming both players play optimally.

Input

The input consists of three lines, each containing numbers separated by spaces, representing the current grid position. A cell with $0$ indicates it is empty, while any other number indicates a placed digit.

Output

In the first line of the output, print the result of the game: $0$ if it's a draw, $1$ if the player who started the game wins (note: this is not necessarily the player who is about to move), or $2$ if the player who went second wins.

Examples

Example 1