D. Scary Subsequences
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

In this problem, all strings consist only of four characters: $$$\texttt{a}$$$, $$$\texttt{b}$$$, $$$\texttt{c}$$$, and $$$\texttt{d}$$$.

Busy Beaver has three strings $$$x$$$, $$$y$$$, and $$$z$$$ that he's really scared of. In particular, he only likes strings that are not a subsequence$$$^{\text{∗}}$$$ of any of them.

Answer $$$Q$$$ queries. In query $$$i$$$, you are given a string $$$s_i$$$, such that $$$x$$$, $$$y$$$, and $$$z$$$ are all subsequences of $$$s_i$$$ and $$$|s_i| \gt \max(|x|, |y|, |z|)$$$. Help Busy Beaver find the length of the shortest subsequence of $$$s_i$$$ that is not a subsequence of any of $$$x$$$, $$$y$$$, or $$$z$$$.

$$$^{\text{∗}}$$$A string $$$s$$$ is a subsequence of a string $$$t$$$ if $$$s$$$ can be obtained from $$$t$$$ by deleting some (possibly none or all) characters from $$$t$$$, without reordering the remaining characters.

Input

The first three lines of the input contain the strings $$$x$$$, $$$y$$$, and $$$z$$$ ($$$1 \le |x|, |y|, |z| \le 60$$$), consisting of characters $$$\texttt{a}$$$, $$$\texttt{b}$$$, $$$\texttt{c}$$$, $$$\texttt{d}$$$.

The next line contains a single positive integer $$$Q$$$ ($$$1 \le Q \le 1.5 \cdot 10^5$$$).

The next $$$Q$$$ lines each contain a string, the $$$i$$$-th of which is $$$s_i$$$ ($$$\max(|x|, |y|, |z|) \lt |s_i| \leq 3 \cdot 10^5$$$), consisting of characters $$$\texttt{a}$$$, $$$\texttt{b}$$$, $$$\texttt{c}$$$, $$$\texttt{d}$$$ such that $$$s_i$$$ has $$$x$$$, $$$y$$$, and $$$z$$$ as subsequences.

The sum of $$$|s_i|$$$ over all queries does not exceed $$$3 \cdot 10^5$$$.

Output

On the $$$i$$$-th line, output a single positive integer — the shortest possible length of a subsequence of $$$s_i$$$ that is not a subsequence of any of $$$x$$$, $$$y$$$, or $$$z$$$.

Example
Input
abb
bcc
abcc
3
abcbc
dabcabc
abbcc
Output
2
1
3
Note

In the first query, all length $$$1$$$ subsequences of $$$\texttt{abcbc}$$$ are subsequences of one of $$$x$$$, $$$y$$$, or $$$z$$$, but the subsequence $$$\texttt{cb}$$$ is not, so the answer is $$$2$$$.

In the second query, $$$\texttt{d}$$$ is a subsequence of $$$\texttt{dabcabc}$$$ that is not a subsequence of any of $$$x$$$, $$$y$$$, or $$$z$$$.

In the third query, $$$\texttt{bbc}$$$ is a subsequence of $$$\texttt{abbcc}$$$ that is not a subsequence of any of $$$x$$$, $$$y$$$, or $$$z$$$, and it is the shortest such subsequence.