该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

须弥遥遥无期，但是小H早已准备好了原石抽小吉祥。已经等不住的他无聊的在纸上写着小吉祥的缩写，xjxjxjx...

题目描述

给你一个长度为n的字符串，其只由小写字符"x"和"j"构成，接下来会有k次询问，每次询问会给出两个正整数l和r。对于每一次询问你需要回答从l到r这一段当中有多少个"xjx"，即这一段当中有多少个长度为3的子串是"xjx"。

提示：子串是指原字符串通过删除若干个前缀的字符或若干个后缀的字符得到的字符串。

输入格式

第一行包含两个正整数n和k分别代表所给字符串的长度以及询问的次数(1$\leqslant$n,k$\leqslant$100000)

第二行包含一个长度为n的字符串，字符串只有小写字符"x"和"j"构成

接下来k行每行包含两个正整数l和r(1$\leqslant$l$\leqslant$r$\leqslant$n)

输出格式

输出共k行，其中第i行输出第i次询问的结果

样例 #1

样例输入 #1

6 2
xxjxjx
2 6
3 6

样例输出 #1

2
1