E. Редактор с быстрым перемещением
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задана строка $$$s$$$, состоящая из строчных латинских букв.

Курсор изначально находится между двумя соседними буквами строки. Курсор не может стоять до первой или после последней буквы.

Вы можете совершить любое количество действий с курсором (возможно, ноль). Каждое действие должно быть одного из трех типов:

  • подвинуть курсор на одну позицию влево (если это не поместит его до первой буквы);
  • подвинуть курсор на одну позицию вправо (если это не поместит его после последней буквы);
  • пусть $$$x$$$ — буква сразу слева от курсора, а $$$y$$$ — буква сразу справа. Вы можете выбрать любую пару соседних букв в строке, такую, что левая буква в паре тоже $$$x$$$, а правая тоже $$$y$$$, и переместить курсор в позицию между этими двумя буквами.

Вы должны обработать $$$m$$$ запросов. В каждом запросе задаются два целых числа $$$f$$$ и $$$t$$$, описывающих корректные позиции курсора в строке; в качестве ответа на запрос вы должны вывести минимальное количество действий, требуемое, чтобы переместить курсор из позиции $$$f$$$ в позицию $$$t$$$.

Входные данные

В первой строке записана строка $$$s$$$ ($$$2 \le |s| \le 5 \cdot 10^4$$$), состоящая из строчных латинских букв.

Во второй строке записано одно целое число $$$m$$$ ($$$1 \le m \le 5 \cdot 10^4$$$) — количество запросов.

В $$$i$$$-й из следующих $$$m$$$ строк записаны два целых числа $$$f$$$ и $$$t$$$ ($$$1 \le f, t \le |s| - 1$$$) — начальная и конечная позиции курсора в $$$i$$$-м запросе. Позиция $$$x$$$ означает, что курсор находится между $$$x$$$-й и $$$(x+1)$$$-й буквами строки (в $$$1$$$-индексации).

Выходные данные

На каждый запрос выведите одно целое число — минимальное количество действий, необходимое, чтобы передвинуть курсор из позиции $$$f$$$ в позицию $$$t$$$.

Примеры
Входные данные
codecode
3
1 7
3 5
3 6
Выходные данные
3
2
2
Входные данные
abcdefghij
3
1 9
9 1
5 5
Выходные данные
8
8
0
Входные данные
aaaaaaaaaaaa
4
10 8
3 7
6 1
11 11
Выходные данные
1
1
1
0