题目描述

小明完成了这样一个数字生成游戏，对于一个不包含$0$的数字$s$来说，有以下$3$种生成新的数的规则：

1. 将$s$的任意两位对换生成新的数字，例如$143$可以生成$314,413,134$；

2. 将$s$的任意一位删除生成新的数字，例如$143$可以生成$14,13,43$

3. 在$s$的相邻两位之间$s_i,s_{i + 1}$之间插入一个数字x，x需要满足$s_i<x<s_{i + 1}$。例如$143$可以生成$1243,1343$，但是不能生成$1143,1543$等。

现在小明想知道，在这个生成法则下，从$s$开始，每次生成一个数，可以用然后用新生成的数生成另外一个数，不断生成直到生成$t$至少需要多少次生成操作。

另外，小明给规则$3$又加了一个限制，即生成数的位数不能超过初始数$s$的位数。若$s$是$143$，那么$1243$与$1343$都是无法生成的；若$s$为$1443$，那么可以将$s$删除变为$143$，再生成$1243$或$1343$。

输入格式

第一行包含$1$个正整数，为初始数字$s$。

第二行包含一个正整数$m$，为询问个数。

接下来$m$行，每行一个整数$t$（$t$不包含$0$），表示询问从$s$开始不断生成数字到$t$最少要进行多少次操作。任两个询问独立，即上一个询问生成过的数到下一个询问都不存在，只剩下初始数字$s$。

输出格式

共$m$行，每行一个正整数，对每个询问输出最少操作数，如果无论如果无论也变换不成，则输出$-1$。

143
3
134
133
32

1
-1
4

提示

$143$ ->$134$

$133$无法得到

$143$ -> $13$ -> $123$ ->$23$->$32$

对于$20\%$的数据，$s < 100$；
对于$40\%$的数据，$s < 1000$；
对于$40\%$的数据，$m < 10$；
对于$60\%$的数据，$s < 10000$；
对于$100\%$的数据，$s < 100000,m ≤ 50000$。