АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

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

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

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

Input

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

Дараагийн мөрөнд нийт хүсэлтийн тоо m (1 ≤ m ≤ 10⁵) өгөгдөнө. Хүсэлт бүрийн хувьд l,r (1 ≤ l_i< r_i≤ 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