Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

RGB7553 - Илья болон хүсэлт

Ильягийн найзууд бүгдээрээ шалгалтан дээр бие биедээ туслахыг хүсдэг. IT-гийн шалгалтан дээр дараах асуудал гарж ирсэн.

Бид нарт s = s1s2...sn (n урттай ), зөвхөн "." болон "#" -с тогтсон тэмдэгт мөр өгөгдөнө. Бидэнд m ширхэг хүсэлт өгөгдөнө. Хүсэлт бүр нЬ li, ri (1 ≤ li< ri≤ n) гэсэн хоёр бүхэл тооноос тогтоно. Зэрэгцэж суусан хоёр ижил вариант авсан хүүхдүүд хоорондоо туслах боломжтой өөрөөр хэлбэл вариантууд si == si+1 i(li≤ i < ri) бол нэгэндээ тусалж болно.

l-с r завсарт нийт хэдэн хүүхэд нэгэндээ тусалж болохыг тооцоолно уу.

Input

Эхний мөрөнд n(2 ≤ n ≤ 105) урттай s тэмдэгт мөр өгөгдөнө. Зөвхөн "." болон "#"тэмдэгтээс тогтсон байна.

Дараагийн мөрөнд нийт хүсэлтийн тоо (1 ≤ m ≤ 105) өгөгдөнө. Хүсэлт бүрийн хувьд l,(1 ≤ li< ri≤ n). хоёр бүхэл тоо өгөгдөнө.

Output

Хүсэлт бүрийн хувьд өгөгдсөн дарааллаар харгалзах утгыг хэвлэ.

Example

Input 1:

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

Output 1:

1
1
5
4

Input 2:

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

Output 2:

1
1
2
2
0


Нэмсэн:Bataa
Огноо:2014-03-26
Хугацааны хязгаарлалт:1s
Эх кодын хэмжээний хязгаарлалт:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Програмчлалын хэлүүд:ADA95 ASM32 BASH BF C NCSHARP CSHARP C++ 4.3.2 CPP C99 CLPS LISP sbcl LISP clisp D ERL FORTRAN HASK ICON ICK JAVA JS-RHINO JULIA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON PYPY3 PYTHON3 RUBY SCALA SCM guile ST TCL WHITESPACE
Эх сурвалж:Codeforces.com

hide comments
2019-11-17 07:23:08
bot: yu be yuun de jangum chi uhchee bzdee
2019-11-17 07:22:52
de jangum: hool hiij oghuu
2019-11-17 07:22:37
sor: ahh i love you bejuu dont die pls
2019-11-17 07:22:15
bot: yuu???
2019-11-17 07:22:05
sor : i love bot pls marryy me
2019-11-17 07:22:01
g

Last edit: 2019-11-17 07:28:52
2019-11-17 07:22:00
bejuu: ahh hort havdar tuschlaa
2019-11-17 07:21:25
admin Lkick sor
2019-11-17 07:21:11
bot: really
2019-11-17 07:20:58
sor:i hate u bot
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.