Задача 39356. Get OK

Given a string S of length N, consisting of the characters S, T, O and K. Answer Q requests like the following.
Query i(1 <= i <= Q): for given integers li and r i (1 <= l_i< r_i <= N),  the substring S is considered, starting at index li and ending at index ri < /sub> (both inclusive). You need to determine how many times OK  occurs as a substring in this string?
 

Explanation

A substring of a string is a string obtained by removing zero or more characters from the beginning and end of the string of the original string. For example, for the string KOTS, the substrings would be the strings KO, KOT , OT, OTS, (empty string) and others, but not OK.


Input
The first line contains two numbers N (2<=N<=10⁵) and Q (1<=Q<=10⁵). The second line contains a string S of length N. Each character in the string is S, T, O or K. Next come Q lines of 2 numbers each: li and r_i < /code>(1 <= l_i< r_i <= N).

Imprint
Print Q lines. The Ith line should contain the response to the ith request.
 

Examples

#	Input	Output
1	8 3 OKOKTOKS 37 23 18	2 0 3