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

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

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

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

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