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

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

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

Оролт

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

Дараагийн мөрөнд нийт хүсэлтийн тоо $m (1 ≤ m ≤ 10^5) $ өгөгдөнө. Хүсэлт бүрийн хувьд $l , r(1 ≤ l_i < r_i ≤ n).$ хоёр бүхэл тоо өгөгдөнө.

Гаралт

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