Description

Xiaoming has completed a number generation game. For a number $s$ that does not contain the digit $0$, there are the following $3$ rules to generate new numbers:

1. Swap any two digits of $s$ to form a new number. For example, $143$ can generate $341, 413, 134$.

2. Delete any single digit of $s$ to form a new number. For example, $143$ can generate $14, 13, 43$.

3. Insert a digit $x$ between two adjacent digits $s_i, s_{i + 1}$ of $s$, where $x$ must satisfy $s_i < x < s_{i + 1}$. For example, $143$ can generate $1243, 1343$, but cannot generate $1143, 1543$, etc.

Now Xiaoming wants to know, under these rules, starting from $s$, each step generating a new number (and then using the newly generated number to generate the next one), what is the minimum number of operations required to obtain $t$.

Additionally, Xiaoming imposes a further restriction on rule $3$: the number of digits of any generated number cannot exceed the number of digits of the initial number $s$. If $s$ is $143$, then $1243$ and $1343$ are impossible to generate. If $s$ is $1443$, then you can first delete a digit to obtain $143$, and then generate $1243$ or $1343$.

Input Format

The first line contains $1$ positive integer, the initial number $s$.

The second line contains a positive integer $m$, the number of queries.

The next $m$ lines each contain an integer $t$ ($t$ does not contain the digit $0$), asking for the minimum number of operations needed to generate $t$ starting from $s$. Any two queries are independent; numbers generated in one query do not carry over to the next, and only the initial number $s$ remains.

Output Format

Output $m$ lines. For each query, output one positive integer: the minimum number of operations. If it is impossible to transform under the rules, output $-1$.

143
3
134
133
32

1
-1
4

Hint

Sample explanation:

$143 \to 134$

$133$ cannot be obtained.

$143 \to 13 \to 123 \to 23 \to 32$

Constraints

For $20\%$ of the testdata, $s < 100$. For $40\%$ of the testdata, $s < 1000$. For $40\%$ of the testdata, $m < 10$. For $60\%$ of the testdata, $s < 10000$. For $100\%$ of the testdata, $s < 100000, m \leq 50000$.

Translated by ChatGPT 5