Задачи
Вычти подстроку
Вычти подстроку
На доске написано натуральное число \textbf{n}. Аким Сергеевич и Маша из \textbf{A'} делают ходы по очереди.
Каждым ходом игрок выбирает натуральное число \textbf{m}, являющееся собственной подстрокой числа, написанного в данный момент на доске, и из числа на доске вычитается \textbf{m}.
Например, если на доске написано \textbf{2309}, игрок может выбрать \textbf{m = 2}, \textbf{3}, \textbf{9}, \textbf{23}, \textbf{30}, \textbf{230} или \textbf{309}. Таким образом, после этого хода на доске окажется одно из чисел \textbf{2000}, \textbf{2079}, \textbf{2279}, \textbf{2286}, \textbf{2300}, \textbf{2306} и \textbf{2307}.
Игрок, который не может сделать ход, проигрывает.
Первым ходит Аким Сергеевич. Помогите ему обыграть Машу! Найдите минимальное число \textbf{m}, которое ему следует вычесть своим первым ходом, чтобы после этого выиграть игру (при оптимальной игре Маши).
\InputFile
Во входном файле число \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{1000000}).
\OutputFile
Выведите минимальное \textbf{m}, которое следует вычесть Акиму Сергеевичу, чтобы выиграть. Если Аким Сергеевич проигрывает при оптимальной игре Маши, выведите \textbf{-1}.
Входные данные #1
5
Выходные данные #1
-1