Веселі стрибки

Limits: 3 sec., 512 MiB

Зеник і Марічка весело розважаються. Вони мають рядок \(s\) з букв латинського алфавіту і кожного дня намагаються за мінімальну кількість операцій добратися з однієї позиції цього рядка до іншої. Для цього вони можуть робити один із двох видів стрибків:

• Звичайний стрибок: перейти в сусідню позицію ліворуч або праворуч. Якщо поточна позиція знаходиться на краю рядка, то звичайно стрибнути у відповідному напрямку не можна.

• Веселий стрибок: перейти в найближчу позицію ліворуч або праворуч, котра містить таку ж літеру, як і в поточній позиції. Якщо у котромусь із напрямків такої букви нема, то і весело стрибнути в цьому напрямку не вийде.

Зеник і Марічка дуже радіють, коли їм вдається зробити вдалий веселий стрибок, який суттєво зменшує кількість операцій для досягнення мети. Проте вони вважають, що надмірне щастя — це не надто добре, тому щодня дозволяють собі не більше одного веселого стрибка.

Маючи рядок \(s\), а також початкову і кінцеву позиції для кожного дня, скажіть мінімальну кількість операцій, необхідних для того щоб добратися до потрібної позиції, використавши при цьому не більше одного веселого стрибка.

Input

У першому рядку задано рядок \(s\).

У другому рядку задано одне ціле число \(q\) — кількість днів.

У наступних \(q\) рядах задано по два цілих числа розділених пробілом \(a_i\), \(b_i\) — початкова і кінцева позиції для \(i\)-го дня.

Output

Виведіть \(q\) рядків. В \(i\)-му з них виведіть одне ціле число — мінімальну кількість операцій для \(i\)-го дня.

Constraints

\(2 \le |s| \le 5 \cdot 10^5\),

\(1 \le q \le 5 \cdot 10^5\),

\(1 \le a_i, b_i \le |s|\),

\(a_i \neq b_i\),

\(s\) містить лише маленькі латинські літери.

Samples

Input (stdin) сopy	Output (stdout) сopy
abdacaba 7 6 1 1 8 5 8 5 3 7 4 7 3 7 2	3 3 2 2 2 2 1

Notes

На картинці зображено:

• Всі можливі стрибки для рядка \(s\) з прикладу.

• Оптимальні стрибки для позицій \(6\) та \(1\).

• Оптимальні стрибки для позицій \(7\) та \(3\).