一个长度为 的只包含字符 和 的字符串 ，下标从 开始。 每次给出一个区间 ，对下标在区间内（包含左右端点）的字符进行染色，在满足下面两个要求的前提下，最多能染色多少个字符？注意每个询问都是独立的，不会对后续询问造成影响。 1）染色的字符的下标 满足 。 2）不存在任意两个相邻的字符 同时被染色。

输入描述:

第一行包含两个整数 ，表示字符串长度和询问次数。第二行包含一个长度为  且只包含数字  和  的字符串。接下来  行，每行两个整数 ，表示询问区间。

输出描述:

输出包含  行，每行一个整数，表示最多染色的下标。