Лев Илья хочет помочь всем своим друзьям со сдачей экзаменов. Чтобы сдать экзамен по информатике нужно решить следующую задачу.
Даны строка s = s1s2... sn (n — длина строки), состоящая только из символов «.» и «#», и m запросов. Каждый запрос описывается парой целых чисел li, ri (1 ≤ li < ri ≤ n). Ответ на запрос li, ri — это количество таких целых чисел i (li ≤ i < ri), что si = si + 1.
Лев Илья хочет помочь друзьям, но кто же поможет ему. Помогите Льву Илье, решите задачу.
В первой строке записана строка s длины n (2 ≤ n ≤ 105). Гарантируется, что заданная строка состоит только из символов «.» и «#».
В следующей строке записано целое число m (1 ≤ m ≤ 105) — количество запросов. В каждой из следующих m строк записано описание соответствующего запроса. В i-той строке записаны целые числа li, ri (1 ≤ li < ri ≤ n).
Выведите m целых чисел — ответы на запросы в том порядке, в котором запросы заданы во входных данных.
...... 4 3 4 2 3 1 6 2 6
1 1 5 4
#..### 5 1 3 5 6 1 5 3 6 3 4
1 1 2 2 0
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач