← 返回题目列表

Codeforces · 962/C

C. 做一个正方形

中文机器翻译题面 查看原题

给定一个正整数 $$$n$$$,不带前导零(例如,数字 04 是不正确的)。

在一次操作中,您可以删除给定整数的任何数字,以使结果保持为不带前导零的正整数。

确定需要对给定整数 $$$n$$$ 一致应用的最小运算次数,以根据它得出某个正整数的平方,否则报告这是不可能的。

整数 $$$x$$$ 是某个正整数的平方当且仅当 $$$x=y^2$$$ 对于某个正整数 $$$y$$$。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^{9}$$$)。给出的数字不带前导零。

输出

如果无法从 $$$n$$$ 中计算某个正整数的平方,则打印 -1。在另一种情况下,打印完成该操作所需的最少操作数。

示例

输入 #1

8314

输出 #1

2

输入 #2

625

输出 #2

0

输入 #3

333

输出 #3

-1

注意

在第一个示例中,我们应该从 $$$8314$$$ 中删除数字 $$$3$$$ 和 $$$4$$$。之后$$$8314$$$ 就等于$$$81$$$,它是整数$$$9$$$ 的平方。

在第二个示例中,给定的 $$$625$$$ 是整数 $$$25$$$ 的平方,因此您不应删除任何内容。

在第三个示例中,不可能用 $$$333$$$ 制作正方形,因此答案为 -1。