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.
Выходные данные
Для каждой пары выведите строку, содержащую единственное целое число — минимальная длина требуемой подстроки. Если искомой подстроки не существует, выведите -1.
Примечание
Кратчайшие подстроки для первого примера таковы: xyz, dyhduxyz.
Кратчайшие подстроки для второго примера таковы: ca, abc и abd.
Кратчайшие подстроки для третьего примера таковы: baabca и abaa.