题目描述

给定一个包含 $5$ 个数字（$0\sim 9$）的字符串，例如 "02943"，请将 "12345" 变换到它。你可以采取 $3$ 种操作进行变换

1. 交换相邻的两个数字；
2. 将一个数字加 $1$。如果加 $1$ 后大于 $9$，则变为 $0$；
3. 将一个数字加倍。如果加倍后大于 $9$，则将其变为加倍后的结果除以 $10$ 的余数。

最多只能用第 $2$ 种操作 $3$ 次，第 $3$ 种操作 $2$ 次，求最少经过多少次操作可以完成变换。

输入格式

有最多 $10^5$ 组数据，每组数据就是包含 $5$ 个数字的字符串。

输出格式

对每组数据，输出将 "12345" 变换到给定字符串所需要的最少操作步数。如果无法变换成功，输出 $-1$。

12435
99999
12374

1
-1
3

提示

由于测试数据太多，如果对每组数据都从头进行搜索，就会超时。建议先做预处理，即以 "12345" 作为初始状态做一遍彻底的广搜，找出 "12345" 经合法变换能够到达的所有字符串，并记录到达这些字符串各需要多少步操作。然后对读入的每组数据，在上述预处理记录的结果中进行查询即可。