D. DZY любит строки
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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.

Примеры
Входные данные
xudyhduxyz
3
xyz xyz
dyh xyz
dzy xyz
Выходные данные
3
8
-1
Входные данные
abcabd
3
a c
ab abc
ab d
Выходные данные
2
3
3
Входные данные
baabcabaaa
2
abca baa
aa aba
Выходные данные
6
4
Примечание

Кратчайшие подстроки для первого примера таковы: xyz, dyhduxyz.

Кратчайшие подстроки для второго примера таковы: ca, abc и abd.

Кратчайшие подстроки для третьего примера таковы: baabca и abaa.