题目描述

阿瓦在字符串王国中，今天，他找到了一个字符串 $s$，还找到了 $q$ 组字符串 $s1,s2$，对于这 $q$ 组字符串，你都要找出字符串 $s$ 中的一个子串，使得这个子串有 $s1,s2$ 这两个子串，你需要求出这个的最小长度，如果找不到任何子串满足条件，则输出 $-1$。

输入格式

第一行输入一个字符串 $s$。

第二行输入一个正整数 $q$。

之后 $q$ 行每行输入两个字符串 $s1,s2$。

输出格式

输出共 $q$ 行，每行输出一个整数表示你的答案。

输入输出样例 #1

输入 #1

abcd
4
a c
ab cd
b d
ac d

输出 #1

3
4
3
-1

输入输出样例 #2

输入 #2

mfnjnaifhuaihfbsjcsixcbzxjchnazxfhhasuigfuisajfhooieawsfhheufergyretyfgvawfawiofpwoafioqhufhpiwufhuibhdfbahjbfvhjdbvnmbzvnmbvzhcdvhhjzsdvchyhjsagfgefguyawfguwafyoiuoyfuiafpifyuiqwuioiuotruqtgfuygdfghjagfhjfjhdsaghasdfghhasdcvhgzjxnsmfgvhjawegweijwe
12
q ds
a b
d e
p g
dsf sd
af fy
af hh
qw a
a gh
q yt
mfn jwe
fui smf

输出 #2

22
2
13
11
-1
3
29
10
3
-1
248
68

说明/提示

【数据范围】

设 $|s|$ 为字符串 $s$ 的长度。

对于 $20\%$ 的数据，$|s1|,|s2| \le 1$。

对于 $40\%$ 的数据，$|s1|,|s2| \le 2$。

对于 $60\%$ 的数据，$|s1|,|s2| \le 3$。

对于另外 $20\%$ 的数据，$q \le 100$。

对于 $100\%$ 的数据，$1 \le q \le 10^5$，$1 \le |s| \le 5 \times 10^4$，$1 \le |s1|, |s2| \le 4$。