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

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}\).