Ardıcıl

Sizə uzunluğu $n$ olan $s=s_1{s}_2...s_n$ sətir verilib, kiçik ingilis əlifbası hərflərindən ibarətdir.

Bundan əlavə, sizə sətir $s$-ə $q$ sorğu verilib. Hər bir $i=1,2,...,q$ üçün, $i$-ci sorğu iki tam ədəd $l_i$ və $r_i$ ilə təqdim olunur və aşağıdakı kimidir:

• $s$ sətirinin $l_i$-dən $r_i$-yə qədər olan simvollarını əhatə edən $s_{l_i}{s}_{l_{i+1}}...s_{r_i}$ alt sətirində, eyni kiçik ingilis əlifbası hərfinin ardıcıl iki dəfə təkrarlanması ilə neçə yer mövcuddur? Başqa sözlə, neçə tam ədəd $p$ mövcuddur ki, $l_i\le p\le r_i-1$ və $s_p=s_{p+1}$?

Hər bir $q$ sorğu üçün cavabı verin.

Giriş verilənləri

Birinci sətirdə iki tam ədəd $n$ və $q(1\le n,q\le 3\cdot 10^5)$ verilir.

İkinci sətir uzunluğu $n$ olan, kiçik ingilis əlifbası hərflərindən ibarət olan $s$ sətiridir.

Növbəti $q$ sətirin hər biri sorğu $(l_i,r_i),1\le l_i,r_i\le n,1\le i\le q$-ni ehtiva edir.

Çıxış verilənləri

Hər bir $i=1,2,...,q$ üçün, $i$-ci sorğuya cavab olan $q$ sətir verin.

Nümunələr