Задано целое положительное число \(n\), запись которого не содержит лидирующих нулей (например, запись 04 недопустима).
За один ход вы можете удалить любую его цифру так, чтобы результат остался положительным числом без лидирующих нулей.
Определите минимальное количество операций, которые можно последовательно применить, чтобы сделать заданное число \(n\) квадратом некоторого целого положительного числа, либо сообщите, что это невозможно.
Целое число \(x\) является квадратом некоторого целого положительного числа, если \(x=y^2\) для некоторого целого положительного \(y\).
Выходные данные
Если невозможно сделать из числа \(n\) с помощью описанных операций квадрат некоторого целого положительного числа, выведите -1. В противном случае, выведите минимальное количество операций, которые необходимы для этого.
Примечание
В первом примере из числа \(8314\) нужно удалить цифру \(3\) и цифру \(4\). После этого \(8314\) станет равно числу \(81\), которое является квадратом числа \(9\).
Во втором примере число \(625\) изначально является квадратом числа \(25\), поэтому ничего удалять не нужно.
В третьем примере невозможно получить из числа \(333\) квадрат целого числа, поэтому ответ на этот примере -1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8314
|
2
|
|
2
|
625
|
0
|
|
3
|
333
|
-1
|