题目描述

小明完成了这样一个数字生成游戏，对于一个不包含 $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\to 134$

$133$ 无法得到

$143\to13\to123\to23\to32$

数据范围

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