Subtract the substring
On the board, a natural number n is written. Akim Sergeyevich and Masha from A' take turns making moves.
During each turn, a player selects a natural number m, which is a proper subsequence of the number currently displayed on the board, and subtracts m from it.
For instance, if the number on the board is 2309, a player can choose m to be 2, 3, 9, 23, 30, 230, or 309. Consequently, after this move, the number on the board will become one of 2000, 2079, 2279, 2286, 2300, 2306, or 2307.
The player who cannot make a move loses.
Akim Sergeyevich takes the first turn. Help him defeat Masha! Determine the minimum number m he should subtract on his first move to ensure a win (assuming Masha plays optimally).
Input
The input file contains the number n (1 ≤ n ≤ 1000000).
Output
Output the minimum m that Akim Sergeyevich needs to subtract to win. If Akim Sergeyevich cannot win with Masha playing optimally, output -1.