На дошці записано натуральне число . Акім Сергійович і Маша з A' роблять ходи по черзі.
Кожного ходу гравець вибирає натуральне число , яке є власним (неповним) підрядком числа, що написано на дошці, і віднімає від цього числа.
Наприклад, якщо на дошці написано , гравець може вибрати , яке дорівнює 2, 3, 9, 23, 30, 230 або . Після цього на дошці залишиться одне з чисел 2000, 2079, 2279, 2286, 2300, 2306 або .
Гравець, який не може зробити хід, програє.
Першим ходить Акім Сергійович. Допоможіть йому виграти у Маші! Знайдіть мінімальне число , яке він має відняти першим ходом, щоб виграти партію (за умови оптимальної гри Маші).
У вхідному файлі міститься число (1 \leq n \leq 1000000).
Виведіть мінімальне , яке повинен відняти Акім Сергійович для перемоги. Якщо Акім Сергійович не може виграти при оптимальній грі Маші, виведіть -1.
Приклад 1