Відніми підрядок#5448

Відніми підрядок

1 секунда
64 мегабайти
Легка

На дошці записано натуральне число . Акім Сергійович і Маша з A' роблять ходи по черзі.

Кожного ходу гравець вибирає натуральне число , яке є власним (неповним) підрядком числа, що написано на дошці, і віднімає від цього числа.

Наприклад, якщо на дошці написано , гравець може вибрати , яке дорівнює 2, 3, 9, 23, 30, 230 або . Після цього на дошці залишиться одне з чисел 2000, 2079, 2279, 2286, 2300, 2306 або .

Гравець, який не може зробити хід, програє.

Першим ходить Акім Сергійович. Допоможіть йому виграти у Маші! Знайдіть мінімальне число , яке він має відняти першим ходом, щоб виграти партію (за умови оптимальної гри Маші).

Вхідні дані

У вхідному файлі міститься число (1 \leq n \leq 1000000).

Вихідні дані

Виведіть мінімальне , яке повинен відняти Акім Сергійович для перемоги. Якщо Акім Сергійович не може виграти при оптимальній грі Маші, виведіть -1.

Приклади

Приклад 1

Loading
Loading