Hongjun Likes Strings

Hongjun likes strings, so he keeps making up problems about them.

Here is one of them. Given a string $S$ and two strings $A$ and $B$, find the shortest contiguous substring of $S$ that contains both $A$ and $B$ as substrings. The occurrence of $A$ and the occurrence of $B$ are allowed to overlap.

Hongjun is smart, so he solved that at once. Then he thought of a harder version, in which the two strings $A$ and $B$ arrive as $Q$ separate questions. He could not find a fast way to answer them, so he decided that short $A$ and $B$ would let him solve it quickly.

Help Hongjun and write a program that answers every question.

The first line contains a string $S$ of length at most $50\,000$.

The second line contains the number of questions $Q$, an integer with $0 \le Q \le 100\,000$.

Each of the next $Q$ lines contains two strings $A$ and $B$ separated by a space. The length of $A$ and the length of $B$ are between $1$ and $4$.

$S$, $A$, and $B$ consist of lowercase English letters only.

Print the answers to the $Q$ questions, one per line. On each line print the minimum length of a contiguous substring of $S$ that contains both $A$ and $B$ as substrings. If no such contiguous substring exists, print $-1$.