제곱수 만들기

앞에 불필요한 영이 없이 표기된 양의 정수 n이 주어진다(예를 들어, 수 04는 올바르지 않다).

한 번의 연산으로 주어진 정수의 임의의 자릿수를 삭제할 수 있으며, 그 결과는 앞에 불필요한 영이 없는 양의 정수로 남아 있어야 한다.

주어진 정수 n에 연산을 계속 적용하여 어떤 양의 정수의 제곱으로 만드는 데 필요한 연산의 최소 횟수를 구하거나, 불가능하다고 보고한다.

정수 x이 어떤 양의 정수의 제곱인 것은 어떤 양의 정수 y에 대해 x=$y^2$일 때, 그리고 그럴 때에만 성립한다.

첫째 줄에 하나의 정수 n (1 ≤ n ≤ 2 ⋅ $10^{9}$)이 주어진다. 이 수는 앞에 불필요한 영이 없이 주어진다.

n에서 어떤 양의 정수의 제곱을 만드는 것이 불가능하면 -1을 출력한다. 그 외의 경우에는 이를 위해 필요한 연산의 최소 횟수를 출력한다.

첫 번째 예제에서는 8314에서 숫자 3과 4를 삭제해야 한다. 그러면 8314는 81이 되며, 이는 정수 9의 제곱이다.

두 번째 예제에서 주어진 625는 정수 25의 제곱이므로 아무것도 삭제하지 않아야 한다.

세 번째 예제에서는 333으로 제곱수를 만드는 것이 불가능하므로 답은 -1이다.