无题---------------搜索

题目描述

AliceAlice 最近得到了一个正整数 xx。由于 BobBob 的生日马上就要到了，AliceAlice 准备把 xx 作为 BobBob 的生日礼物。 然而 BobBob 只喜欢完全平方数，AliceAlice 为了让 BobBob 开心，打算对 xx 进行一些修改。每次 AliceAlice 可以对 xx 进行如下的一种修改：

1. 将 xx 10进制表示下（不含前导 00）的一个数字修改成 0,\ 1,\ ...,\ 90, 1, ..., 9 中的一个。例如 123123 可以变成 133133，10011001可以变成 11。

2.将 xx 10进制表示下（不含前导 00）的一个数字删去。例如 123123 可以变成 23,\ 1323, 13，10011001 可以变成 11。

注意，必须保证修改后的数字 xx 仍然是正整数。

由于 BobBob 的生日很快就要到了，AliceAlice 想知道最少进行多少次操作（可以不操作）可以将数字 xx 变成完全平方数。

完全平方数的定义：我们成一个数 xx 是完全平方数，当且仅当存在一个自然数 yy 使得 x\ =\ y^2x = y2。

输入输出格式

输入格式：

每个测试点共 TT 组数据。

第一行一个正整数 TT。

接下来 TT 行，每行一个正整数 xx，如题面所述。

输出格式：

输出共 TT 行，每行一个整数表示答案。

输入输出样例

3
1
12
9004

0
1
1

说明

对于 30% 的数据 1\ \leq\ n\ \leq\ 1001 ≤ n ≤ 100。

对于 100% 的数据 1\ \leq\ n\ \leq\ 1000000,\ 1\ \leq\ T\ \leq\ 10001 ≤ n ≤ 1000000, 1 ≤ T ≤ 1000。

无题---------------搜索

原文：https://www.cnblogs.com/wyher/p/9826150.html