Задана строка \(s\), состоящая из строчных латинских букв.
Курсор изначально находится между двумя соседними буквами строки. Курсор не может стоять до первой или после последней буквы.
Вы можете совершить любое количество действий с курсором (возможно, ноль). Каждое действие должно быть одного из трех типов:
- подвинуть курсор на одну позицию влево (если это не поместит его до первой буквы);
- подвинуть курсор на одну позицию вправо (если это не поместит его после последней буквы);
- пусть \(x\) — буква сразу слева от курсора, а \(y\) — буква сразу справа. Вы можете выбрать любую пару соседних букв в строке, такую, что левая буква в паре тоже \(x\), а правая тоже \(y\), и переместить курсор в позицию между этими двумя буквами.
Вы должны обработать \(m\) запросов. В каждом запросе задаются два целых числа \(f\) и \(t\), описывающих корректные позиции курсора в строке; в качестве ответа на запрос вы должны вывести минимальное количество действий, требуемое, чтобы переместить курсор из позиции \(f\) в позицию \(t\).
Выходные данные
На каждый запрос выведите одно целое число — минимальное количество действий, необходимое, чтобы передвинуть курсор из позиции \(f\) в позицию \(t\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
codecode
3
1 7
3 5
3 6
|
3
2
2
|
|
2
|
abcdefghij
3
1 9
9 1
5 5
|
8
8
0
|
|
3
|
aaaaaaaaaaaa
4
10 8
3 7
6 1
11 11
|
1
1
1
0
|