题目描述

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

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

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

输入

有最多 $100,000$组数据 每组数据就是包含$5$个数字的字符串

输出

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

样例

12435
99999
12374

1
-1
3

提示

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