当前没有测试数据。

【题目描述】

Anihc国提高社会生产力水平，落实好以人民为中心的发展思想。决定进行供给侧结构性改革。

为了提高供给品质，你调查乐某个产业近来n个时期的供求关系平衡情况，每个时期的情况用0或1中的一个数字表示，于是这就是一个长度为n的01字符串S。为了更好的了解这一些数据，你需要解决一些询问，我们令data(l,r)表示：在字符串S中，起始位置在[l,r]之间的这些后缀之中，具有最长公共前缀的长度。

对于每一个询问L,R，求

由于你其实根本没时间调查，所以这些数据都是乱编的，即串S中的每一位都是在0和1之间随机产生的。

【输入格式】

第一行2个整数n,Q，表示字符串的长度，以及询问个数。

接下来一行长度为n的一个01串S。

接下来Q行，每行两个整数L,R，表示一个询问[L,R]。

【输出格式】

共Q行，每行一个整数，表示对应询问的答案。

【样例输入】

6 3
010110
2 5
1 6
1 2

【样例输出】

4
6
0

【数据规模与约定】