Ilya và các truy vấn

Cho xâu $s=s_1{s}_2\dots s_n$ độ dài $n$, chỉ gồm hai ký tự . và #, cùng $m$ truy vấn. Mỗi truy vấn là một cặp số nguyên $l_i,r_i$ ($1\le l_i<r_i\le n$).

Với mỗi truy vấn, hãy đếm số chỉ số $i$ thỏa mãn $l_i\le i<r_i$ và $s_i=s_{i+1}$.

Dữ liệu vào

• Dòng đầu chứa xâu $s$ có độ dài $n$, chỉ gồm các ký tự . và #.
• Dòng thứ hai chứa số nguyên $m$ — số truy vấn.
• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $l_i,r_i$.

Dữ liệu ra

In ra $m$ dòng, mỗi dòng là đáp án của truy vấn tương ứng theo thứ tự đầu vào.

Ràng buộc

• $2\le n\le {10}^5$
• $1\le m\le {10}^5$
• $1\le l_i<r_i\le n$

Ví dụ