Problem: 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 = s1s2... sn (n is the length of the string), consisting only of characters "." and "#" and m queries. Each query is described by a pair of integers li, ri (1 ≤ li < ri ≤ n). The answer to the query li, ri is the number of such integers i (li ≤ i < ri), that si = si + 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 ≤ 105). It is guaranteed that the given string only consists of characters "." and "#".

The next line contains integer m (1 ≤ m ≤ 105) — the number of queries. Each of the next m lines contains the description of the corresponding query. The i-th line contains integers li, ri (1 ≤ li < ri ≤ 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

Solution (in PYTHON3):

Solution:
import sys
import collections
import math
import functools
import itertools
import bisect
import operator
import heapq
import random
true=True
false=False
null=None
tcid=0
tcmax=99999999
def compute(val, func): return func(val)
def seq(lo,hi,step=1): 
 return range(lo,hi+1,step)
def sround(val,nd):
 return f'{val:.{nd}f}'
def ceil(a,b):
 ans=a//b
 if a%b!=0: ans+=1
 return ans
def perr(*args,**kwargs): print(*args,file=sys.stderr,**kwargs)
def line():
 ln=sys.stdin.readline().strip()
 #perr(ln)
 if ln=='': sys.exit()
 return ln
def lines(n): return [line() for i in range(n)]
def split(ln=None): return (ln or line()).split()
def nums(o=None,parser=eval):
 if o is not None:
  if isinstance(o, int): o=lines(o)
  elif isinstance(o, str): o=split(o)
 return list(map(parser, o or split()))
def num(parser=eval): return parser(line())
#
#help("sys.modules")
"""
ceil(a,b) sround(val,nd) true false null
num() nums(?) split(?) lines(n) line()
perr(print) tcmax seq() compute(v,f) tcid
"""
#{#

#}#
def mainloop(tcid=1):
# {{{
    s=line()
    aa=[0]*111111
    for ii in range(1,len(s)):
        if s[ii]==s[ii-1]:
            aa[ii]=1
        aa[ii]+=aa[ii-1]
    m=num()
    buffer=[]
    for _ in range(m):
        l,r=nums(parser=int)
        buffer.append(aa[r-1]-aa[l-1])
    print(*buffer,sep="\n")
# }}}
while tcid<tcmax:
 tcid+=1
 mainloop(tcid)
"""
NOTES = .

"""
"""
PROBLEM #ID = .
10137
"""