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