Subtract the substring#5448

Subtract the substring

1 second
64 megabytes
Easy

On the board, a natural number is written. Akim Sergeyevich and Masha from A' take turns making moves.

During each turn, a player selects a natural number which is a proper contiguous substring of the number currently displayed on the board, and subtracts from it.

For example, if the number on the board is , a player can choose to be 2, 3, 9, 23, 30, 230 or . Consequently, after this move, the number on the board will become one of 2000, 2079, 2279, 2286, 2300, 2306 or .

The player who cannot make a move loses.

Akim Sergeyevich makes the first move. Help him defeat Masha! Find the minimum number he should subtract on his first move to ensure a win (assuming Masha plays optimally).

Input

The input file contains the number (1 \leq n \leq 1000000).

Output

Output the minimal that Akim Sergeyevich needs to subtract to win. If Akim Sergeyevich cannot win with Masha playing optimally, output -1.

Examples

Example 1

Loading
Loading