Migrated from Lutece 1385 卿大爷的两个女友

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

卿大爷发现了一个字符串，他要在上面找到两个女朋友的名字。他的女朋友分别叫做$s1,s2$。为了后宫的和谐，他希望这两个人名字能被包含在一个最短的子串（可重叠）里面。他希望你帮他找到这个最短的长度，或者提醒他他没有女朋友的事实。卿大爷会请你帮忙很多次，对于每次询问的$s1,s2$都请你做出回答。

Input

第一行，字符串$s$，$1<=|s|<=50000$，均由小写字母构成。 第二行一个数字$Q$，代表有$Q$次询问$(1<=Q<=100000)$ 接下来Q行，每行有两个字符串$s1,s2$以一个空格隔开（同样均由小写字母构成，$1<=|s1|,|s2|<=4$）

Output

对于每个询问，输出符合要求子串的最短长度，如果没有输出$-1$。

Samples

dlxiplqqsc
3
qsc qsc
xip qsc
liao qsc

3
8
-1

Resources

2016 UESTC Training for Search Algorithm & String