Коля, Вася і двері

Limits: 2 sec., 256 MiB

Намалювавшись досхочу, Коля і Вася нарешті таки добралися до дверей, які вони дійсно повинні були помалювати. Але після стількох розмальованих дверей просто малювати їм було не цікаво. Вони вирішили зіграти в гру. Оскільки будівельники весь день мали справу з фарбою, то правила гри, яку вони придумали, вийшли доволі дивними.

На початку гри будівельники обирають деякий рядок $s$, який складається виключно з малих латинських літер. Гра відбувається в $n$ раундів. Кожен раунд починається з того, що Коля обирає два числа $l_i$ і $r_i$. Потім Коля записує на дверях ту частину рядка $s$, яка починається з символа з номером $l_i$ і закінчується символом з номером $r_i$ (індексація починається з 1). Завдання Васі — замалювати деякі букви записані Колею так, щоб утворений рядок читався однаково як зліва направо, так і справа наліво.

Ніхто не зрозумів, хто з будівельників виграв і чому їм було так весело, але яка різниця? Вони були щасливі і це головне.

Ваше ж завдання — для кожного раунду гри сказати, скільки мінімально символів міг замалювати Вася, щоб рядок читався однаково з обох боків.

Input

У першому рядку задано рядок $s$ — послідовність малих латинських символів.

Другий рядок містить одне натуральне число $n$ — кількість раундів гри.

У третьому рядку задано $n$ пар чисел $l_i$ та $r_i$ — ліві та праві межі для кожного раунду.

Output

У єдиному рядку виведіть $n$ натуральних чисел — відповіді для кожного раунду.

Constraints

$30 \%$ тестів: $1 \le |s|, n \le 100$,

$70 \%$ тестів: $1 \le |s| \le 10^3, 1 \le n \le 10^5$.

Samples

Input (stdin) сopy	Output (stdout) сopy
cabcbaab 3 1 5 2 6 6 8	2 0 1

Notes

Рядок для першого раунду $\texttt{cabcb}$. Треба видалити обидва символи $\texttt{b}$, або перші два символи. Рядок для другого раунду $\texttt{abcba}$ читається однаково з обох сторін. Для рядка третього раунду $\texttt{aab}$ треба видалити символ $\texttt{b}$.