CF444D.DZY Loves Strings

DZY loves strings, and he enjoys collecting them.

In China, many people like to use strings containing their names' initials, for example: xyz, jcvb, dzy, dyh.

Once DZY found a lucky string s. A lot of pairs of good friends came to DZY when they heard about the news. The first member of the i-th pair has name a__i, the second one has name b__i. Each pair wondered if there is a substring of the lucky string containing both of their names. If so, they want to find the one with minimum length, which can give them good luck and make their friendship last forever.

Please help DZY for each pair find the minimum length of the substring of s that contains both a__i and b__i, or point out that such substring doesn't exist.

A substring of s is a string s__l__s__l + 1... s__r for some integers l, r (1 ≤ l ≤ r ≤ |s|). The length of such the substring is (r - l + 1).

A string p contains some another string q if there is a substring of p equal to q.

DZY 喜欢字符串，也热衷于收集字符串。

在中国，许多人喜欢使用包含自己姓名首字母的字符串，例如：xyz、jcvb、dzy、dyh。

某日，DZY 发现了一个幸运字符串 $ s $。消息传出后，许多好友结伴而来。第 $ i $ 对好友中，第一位的名字为 $ a_i $，第二位的名字为 $ b_i $。每对好友都想知道：幸运字符串 $ s $ 中是否存在一个子串，同时包含他们的名字（即同时包含字符串 $ a_i $ 和 $ b_i $）。若存在，他们希望找到长度最短的这样的子串——因为这能带来好运，并让友谊天长地久。

请帮助 DZY 对每一对好友，找出 $ s $ 中同时包含 $ a_i $ 和 $ b_i $ 的最短子串的长度；若不存在这样的子串，请指出这一点。

字符串 $ s $ 的一个子串是指形如 $ s_l s_{l+1} \dots s_r $ 的字符串，其中 $ l, r $ 为满足 $ 1 \leq l \leq r \leq |s| $ 的整数。该子串的长度为 $ r - l + 1 $。

当字符串 $ p $ 中存在一个等于 $ q $ 的子串时，称 $ p $ 包含字符串 $ q $。

The first line contains a string s (1 ≤ |s| ≤ 50000).

The second line contains a non-negative integer q (0 ≤ q ≤ 100000) — the number of pairs. Each of the next q lines describes a pair, the line contains two space-separated strings a__i and b__i (1 ≤ |a__i|, |b__i| ≤ 4).

It is guaranteed that all the strings only consist of lowercase English letters.

第一行包含一个字符串 $s$（$1 \leq |s| \leq 50000$）。

第二行包含一个非负整数 $q$（$0 \leq q \leq 100000$）—— 表示查询对的数量。接下来的 $q$ 行每行描述一对字符串，每行包含两个由空格分隔的字符串 $a_i$ 和 $b_i$（$1 \leq |a_i|,\,|b_i| \leq 4$）。

保证所有字符串仅由小写英文字母组成。

For each pair, print a line containing a single integer — the minimum length of the required substring. If there is no such substring, output -1.

对于每一对，输出一行，包含一个整数——所需子串的最小长度。如果不存在这样的子串，则输出 $-1$。

The shortest substrings in the first sample are: xyz, dyhduxyz.

The shortest substrings in the second sample are: ca, abc and abd.

The shortest substrings in the third sample are: baabca and abaa.

第一个样例中最短的子串是：xyz、dyhduxyz。

第二个样例中最短的子串是：ca、abc 和 abd。

第三个样例中最短的子串是：baabca 和 abaa。