DZY 喜欢琴弦,并且喜欢收集它们。
在中国,很多人喜欢使用包含名字首字母的字符串,例如:xyz、jcvb、dzy、dyh。
有一次DZY发现了幸运字符串s。很多好朋友得知这个消息后都来到了DZY。第 i 对的第一个成员的名称为 ai,第二个成员的名称为 bi。每一对都想知道幸运字符串中是否有一个子字符串包含他们两个的名字。如果是这样,他们想找到长度最小的,这可以给他们带来好运,让他们的友谊天长地久。
请帮助DZY对每对找到s中同时包含ai和bi的子串的最小长度,或者指出这样的子串不存在。
s 的子串是字符串 slsl + 1... sr 对于某些整数 l, r (1 ≤ l ≤ r ≤ |s|)。该子串的长度为(r - l + 1)。
如果 p 的子串等于 q,则字符串 p 包含另一个字符串 q。
输入
第一行包含字符串 s (1 ≤ |s| ≤ 50000)。
第二行包含一个非负整数 q (0 ≤ q ≤ 100000) — 对的数量。接下来的 q 行中的每一行都描述一对,该行包含两个空格分隔的字符串 ai 和 bi (1 ≤ |ai|, |bi| ≤ 4)。
保证所有字符串仅由小写英文字母组成。
输出
对于每一对,打印一行包含单个整数 - 所需子字符串的最小长度。如果不存在这样的子串,则输出-1。
示例
输入 #1
xudyhduxyz 3 xyz xyz dyh xyz dzy xyz
输出 #1
3 8 -1
输入 #2
abcabd 3 a c ab abc ab d
输出 #2
2 3 3
输入 #3
baabcabaaa 2 abca baa aa aba
输出 #3
6 4
注意
第一个样本中最短的子字符串是:xyz、dyhduxyz。
第二个样本中最短的子字符串是:ca、abc 和 abd。
第三个样本中最短的子字符串是:baabca 和 abaa。