Đo độ ổn định của chuỗi tín hiệu

Bối cảnh và bài toán

Một chuỗi tín hiệu chỉ gồm hai trạng thái . và #. Với một đoạn được chọn, kỹ sư muốn biết có bao nhiêu vị trí mà trạng thái tại vị trí đó giống hệt vị trí ngay sau nó. Có rất nhiều truy vấn trên cùng một chuỗi không thay đổi.

Yêu cầu

Với mỗi đoạn [l,r], đếm số chỉ số i thỏa l <= i < r và s[i] = s[i+1].

Input

• Dòng 1: chuỗi s.
• Dòng 2: số truy vấn q.
• q dòng tiếp theo: l r.

Output

In đáp án của từng truy vấn trên một dòng.

Ràng buộc

• 2 <= |s| <= 10^5
• s[i] thuộc {., #}
• 1 <= q <= 10^5
• 1 <= l < r <= |s|

Chấm điểm

Ví dụ 1

Input

......
4
3 4
2 3
1 6
2 6

Output

1
1
5
4

Giải thích. Trong chuỗi toàn dấu chấm, mọi cặp kề đều giống nhau; đoạn dài L có L-1 cặp như vậy.

Ví dụ 2

Input

#..###
3
1 3
1 5
3 6

Output

1
2
2

Giải thích. Ta đếm trên các cặp kề nằm hoàn toàn bên trong đoạn, không đếm theo số ký tự giống nhau.

Thông tin bài tập

Nguồn: Phỏng theo Codeforces 313B — Ilya and Queries.

Tham khảo: https://codeforces.com/problemset/problem/313/B