Ilya the Lion wants to help all his friends with passing exams. They need to solve the following problem to pass the IT exam.

You've got string s = s_1s_2... s_{n} (n is the length of the string), consisting only of characters "." and "#" and m queries. Each query is described by a pair of integers l_{i}, r_{i} (1 ≤ l_{i} < r_{i} ≤ n). The answer to the query l_{i}, r_{i} is the number of such integers i (l_{i} ≤ i < r_{i}), that s_{i} = s_{i} + 1.

Ilya the Lion wants to help his friends but is there anyone to help him? Help Ilya, solve the problem.


-----Input-----

The first line contains string s of length n (2 ≤ n ≤ 10^5). It is guaranteed that the given string only consists of characters "." and "#".

The next line contains integer m (1 ≤ m ≤ 10^5) — the number of queries. Each of the next m lines contains the description of the corresponding query. The i-th line contains integers l_{i}, r_{i} (1 ≤ l_{i} < r_{i} ≤ n).


-----Output-----

Print m integers — the answers to the queries in the order in which they are given in the input.


-----Examples-----
Input
......
4
3 4
2 3
1 6
2 6

Output
1
1
5
4

Input
#..###
5
1 3
5 6
1 5
3 6
3 4

Output
1
1
2
2
0

Difficulty: interview

Starter code:

Solutions:
s=input()
t=int(input())

ans=[]
n=len(s)
clue=[0]*n
for i in range(n-1):
    if(s[i]==s[i+1]):
        clue[i]+=1
L=[clue[0]]
for i in range(1,n):
    L.append(L[i-1]+clue[i])

for i in range(t):
    A,B=input().split()
    A=int(A)-1
    B=int(B)-1
    r=0
    x=L[B-1]
    y=L[A-1]
    if(A-1<0):
        y=0
    ans.append(x-y)

for i in range(t):
    print(ans[i])
    


c = ''
d = [0]
for i in input():
  if i == c:
    d.append(d[-1] + 1)
  else:
    d.append(d[-1])
  c = i
for i in range(int(input())):
  l, r = map(int, input().split())
  print(d[r] - d[l])

c = ''
d = [0]
for i in input():
  if i == c:
    d.append(d[-1] + 1)
  else:
    d.append(d[-1])
  c = i
for i in range(int(input())):
  l, r = map(int, input().split())
  print(d[r] - d[l])

import math
import re
from fractions import Fraction
from collections import Counter

class Task:
    s = ''
    queries = []
    answer = ''
    
    def __init__(self):
        self.s = input()
        self.queries = [[] for _ in range(int(input()))]
        for i in range(len(self.queries)):
            self.queries[i] = [int(x) for x in input().split()]

    def solve(self):
        s, queries = self.s, self.queries
        d = [0] * len(s)
        d[0] = 1 if s[0] == s[1] else 0
        for i in range(1, len(d) - 1):
            d[i] = d[i - 1] + (s[i + 1] == s[i])
        d[-1] = d[-2]

        for current in queries:
            localAnswer = d[current[1] - 2]
            localAnswer -= d[current[0] - 2] if current[0] >= 2 else 0
            #self.answer += str(localAnswer) + '\n'
            print(localAnswer)

    #def printAnswer(self):
    #    print(self.answer)

task = Task()
task.solve()
#task.printAnswer()


import math
import re
from fractions import Fraction
from collections import Counter

class Task:
    s = ''
    queries = []
    answer = []
    
    def __init__(self):
        self.s = input()
        self.queries = [[] for _ in range(int(input()))]
        for i in range(len(self.queries)):
            self.queries[i] = [int(x) for x in input().split()]

    def solve(self):
        s, queries = self.s, self.queries
        d = [0] * len(s)
        d[0] = 1 if s[0] == s[1] else 0
        for i in range(1, len(d) - 1):
            d[i] = d[i - 1] + (s[i + 1] == s[i])
        d[-1] = d[-2]

        for current in queries:
            localAnswer = d[current[1] - 2]
            localAnswer -= d[current[0] - 2] if current[0] >= 2 else 0
            self.answer += [localAnswer]

    def printAnswer(self):
        for x in self.answer:
            print(x)

task = Task()
task.solve()
task.printAnswer()


def main():
    s = input()
    n = int(input())
  
    res = [0]
    for i in range(1,len(s)):
        res.append(res[i-1] + (s[i] == s[i-1]))

    for _ in range(n):
        l,r = map(int,input().split())
        print(res[r-1]-res[l-1])

main()

import sys
import io
fin = io.StringIO(sys.stdin.read())
s = fin.readline().strip()
n = len(s)
table = [0] * n
for i in range(n - 1):
    table[i] = int(s[i] == s[i + 1]) + (table[i - 1] if i > 0 else 0)
m = int(fin.readline())
for _ in range(m):
    l, r = list(map(int, fin.readline().split()))
    print(table[r - 2] - (table[l - 2] if l > 1 else 0))


s=input()
L=[s[i] for i in range(len(s))]
A=[]
ListOfSum=[0]
for i in range(len(L)-1):
    if L[i]==L[i+1]: ListOfSum.append(ListOfSum[i]+1)
    else: ListOfSum.append(ListOfSum[i])
m=int(input())
for i in range(m):
    Z=[int(t) for t in input().split()]
    A.append(ListOfSum[Z[1]-1]-ListOfSum[Z[0]-1])
for i in range(m): print(A[i])

v = input()
n = int(input())
q, s = [], [0 for i in range(-1, len(v))]
sol = ''

for i in range(1, len(v)):
    s[i] = s[i-1]
    if v[i] == v[i-1]: s[i] += 1

for i in range(0, n):
    x = tuple(map(int, input().split()))
    sol += str(s[x[1]-1] - s[x[0]-1]) + '\n'
print(sol)


import sys
f = sys.stdin
#f = open("input.txt", "r")
s = f.readline()
f.readline()
count = [0]
t = ""
q = [map(int, i.split()) for i in f.read().strip().split("\n")]
def solve():
    nonlocal t
    for i in s:
        if i == t:
            count.append(count[-1] + 1)
        else:
            count.append(count[-1])
        t = i
    for i in q:
        l, r = i
        print(count[r]-count[l])
solve()

s = input()
m = int(input())
calc = [0]
out = []
for i in range(1, len(s)):
    count = calc[i-1]
    if s[i] == s[i-1]:
        count += 1
    calc.append(count)
    
for q in range(m):
    L = [int(it) for it in input().split()]
    l, r, count = L[0] - 1, L[1] - 1, 0
    out.append(calc[r] - calc[l])
for c in out:
    print(c)


s=input()
n=int(input())
a,b=[0 for i in range(n)],[0 for i in range(n)]
for i in range(0,n):
    a[i],b[i]=list(map(int,input().split()))
count=[0 for i in range(len(s))]
count[0]=0
for i in range(1,len(s)):
    count[i]=count[i-1]
    if s[i-1]==s[i]:
        count[i]+=1
for i in range(0,n):
    print(count[b[i]-1]-count[a[i]-1])
    
    

        


s=input()
n=int(input())
a,b=[0 for i in range(n)],[0 for i in range(n)]
for i in range(0,n):
    a[i],b[i]=list(map(int,input().split()))
#dp represents a list of the counts to each point in the string
dp=[0]*(len(s))
for i in range(len(s)-1):
    if s[i]==s[i+1]:
        dp[i+1]=dp[i]+1
    else:
        dp[i+1]=dp[i]

for i in range(0,n):
    print(dp[b[i]-1]-dp[a[i]-1])


string=input()
#dp represents a list of the counts to each point in the string
n=int(input())
a,b=[0 for i in range(n)],[0 for i in range(n)]
for i in range(n):
    a[i],b[i]=list(map(int,input().split()))
dp=[0]*(len(string))
for i in range(len(string)-1):
    if string[i]==string[i+1]:
        dp[i+1]=dp[i]+1
    else:
        dp[i+1]=dp[i]
dp.append(dp[-1])

for i in range(n):
    print(dp[b[i]-1]-dp[a[i]-1])


string=input()
#dp represents a list of the counts to each point in the string
n=int(input())
a,b=[0 for i in range(n)],[0 for i in range(n)]
for i in range(n):
    a[i],b[i]=map(int,input().split())
dp=[0]*(len(string))
for i in range(len(string)-1):
    if string[i]==string[i+1]:
        dp[i+1]=dp[i]+1
    else:
        dp[i+1]=dp[i]

for i in range(n):
    print(dp[b[i]-1]-dp[a[i]-1])

s=input()
n=int(input())

l,r=[0 for i in range(n)],[0 for i in range(n)]
for i in range(n):
    l[i],r[i]=list(map(int,input().split()))

d=[0]*len(s)
for i in range(len(s)-1):
    d[i+1]=d[i]
    if(s[i]==s[i+1]):
        d[i+1]=d[i]+1

for i in range(n):
    print(d[r[i]-1]-d[l[i]-1])


s=input()
n=int(input())

l,r=[0 for i in range(n)],[0 for i in range(n)]
for i in range(n):
    l[i],r[i]=list(map(int,input().split()))

d=[0]*len(s)
for i in range(len(s)-1):
    d[i+1]=d[i]
    if(s[i]==s[i+1]):
        d[i+1]=d[i]+1

sol=""
for i in range(n):
    sol+=str(d[r[i]-1]-d[l[i]-1])+"\n"
print(sol)


import sys

l = sys.stdin.readline().strip()
ls = len(l)

c = input()
c = int(c)

r = []

d = []

k = 0
d.append(0)
for i in range (0, ls - 1):
    if l[i] == l[i + 1]:
        k = k + 1
    d.append(k)

for i in range (0, c):
    (n, m) = sys.stdin.readline().strip().split(' ')
    n, m = int(n) - 1, int(m) - 1
    r.append(d[m] - d[n])

for s in r:
    print(s)


import sys
import math

st = sys.stdin.readline()
length = len(st) - 1
an = [0] * length

v = st[0]
for i in range(1,  length):
    k = 0
    if(v == st[i]):
        k = 1
    
    v = st[i]
    an[i] = an[i - 1] + k
    
c = int(sys.stdin.readline())
for i in range(c):
    li,  ri = [int(x) for x in (sys.stdin.readline()).split()]
    print(an[ri - 1] - an[li - 1])
        


s = input()
query_time = int(input())

queries = [list([int(x) - 1 for x in input().split()])
           for _ in range(query_time)]


k = 0
f = [0]
for i in range(len(s) - 1):
    if s[i] == s[i + 1]:
        k += 1
    f.append(k)


for query in queries:
    begin, end = query
    repeat = f[end] - f[begin]

    print(repeat)


magic_string = input()
query_count = int(input())

queries = []
for i in range(query_count):
    queries.append([int(x) for x in input().split()])

saved = [0]
for i in range(1, len(magic_string)):
    saved.append(saved[i - 1] + (1 if magic_string[i-1] == magic_string[i] else 0))

for query in queries:
    print(saved[query[1] - 1] - saved[query[0] - 1])

from fileinput import *

data = []
for line in input():
    if lineno() == 1:
        s = line.strip()
    if lineno() == 2:
        m = int(line.strip())
    if lineno() >= 3 and lineno() < 3 + m:
        data += [list(map(int, line.split()))]

slen = len(s)
a = [0] * slen

count = 0
for i in range(1, slen):
    if s[i] == s[i-1]:
        count += 1
    a[i] = count

for [l, r] in data:
    ll = l - 1
    rr = r - 1
    print(a[rr]-a[ll])


import sys

def solve():
    s = input()
    m = int(input())
    mem = [0] * (len(s) + 1)
    res = list()
    for i in range(1, len(s) + 1):
        mem[i] = mem[i - 1] + (1 if i < len(s) and s[i - 1] == s[i] else 0)
    for query in range(m):
        l, r = map(int, input().split())
        res.append(mem[r - 1] - mem[l - 1])
    print('\n'.join(map(str, res)))
    
if sys.hexversion == 50594544 : sys.stdin = open("test.txt")
solve()