eolymp
bolt
Try our new interface for solving problems
Məsələlər

Вычти подстроку

Вычти подстроку

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

На доске написано натуральное число n. Аким Сергеевич и Маша из A' делают ходы по очереди.

Каждым ходом игрок выбирает натуральное число m, являющееся собственной подстрокой числа, написанного в данный момент на доске, и из числа на доске вычитается m.

Например, если на доске написано 2309, игрок может выбрать m = 2, 3, 9, 23, 30, 230 или 309. Таким образом, после этого хода на доске окажется одно из чисел 2000, 2079, 2279, 2286, 2300, 2306 и 2307.

Игрок, который не может сделать ход, проигрывает.

Первым ходит Аким Сергеевич. Помогите ему обыграть Машу! Найдите минимальное число m, которое ему следует вычесть своим первым ходом, чтобы после этого выиграть игру (при оптимальной игре Маши).

Giriş verilənləri

Во входном файле число n (1n1000000).

Çıxış verilənləri

Выведите минимальное m, которое следует вычесть Акиму Сергеевичу, чтобы выиграть. Если Аким Сергеевич проигрывает при оптимальной игре Маши, выведите -1.

Nümunə

Giriş verilənləri #1
5
Çıxış verilənləri #1
-1