Knight and Elephant Capture

Consider an \(N \times N\) chessboard that has \((N+1) \times (N+1)\) grid points. There are exactly two pieces on the board: a knight and an elephant. The knight moves in an L-shape (similar to the chess knight), i.e. from a position \((x, y)\), it can move to any of the 8 positions:

\( (x+2, y+1), (x+1, y+2), (x-1, y+2), (x-2, y+1), (x-2, y-1), (x-1, y-2), (x+1, y-2), (x+2, y-1) \).

The elephant moves exactly two squares diagonally. That is, from \((x, y)\) it can move to:

\( (x+2, y+2), (x+2, y-2), (x-2, y+2), (x-2, y-2) \).

Initially, the knight is at \((0,0)\) and the elephant is at \((N,N)\). In each turn, one player is allowed to move his piece by performing as many consecutive legal moves as desired (while staying within the board). Either side may start first. Determine whether it is possible for one piece to capture the other (i.e. for both pieces to eventually occupy the same grid point). If it is possible, output the minimum total number of moves (where each individual move counts as one step) required to achieve such a capture. Otherwise, output \(-1\).

Note: A move is defined as one step following the piece's allowed move pattern. The players can coordinate their moves since they are allowed to perform arbitrarily many moves consecutively in their turn.

inputFormat

The input consists of a single integer \(N\) (\(0 \leq N \leq 1000\)), representing the board size. The board has grid points from \((0,0)\) to \((N,N)\). Initially, the knight is at \((0,0)\) and the elephant is at \((N,N)\).

outputFormat

If it is possible to have a capture (i.e. both pieces occupy the same position after some moves), output the minimum total number of moves required. Otherwise, output \(-1\).

sample

1

-1