Description

对于一个01串s，定义函数f(s)为s每一位的异或和，例如f(111)=1,f(110)=0,f(101)=0,f(100)=1。

一个01串s是好串，当且仅当其满足以下条件：

串的长度为2的幂次方。

存在两个非负整数x,b，使得i$\in$[0,|s|-1],si=f(i and x)xorb

（下标从0开始，此处f函数计算的是i and x对应的二进制串的值）。

现对于一个01串，可以使用区间取反操作，即选定一个区间[l,r],0<=l<=r<|s|，

并将[l,r]中的每一位取反（即1->0,0->1）。

现在给出一个长度为n的01串s，q次询问子串sl,r最少经过多少次区间取反操作变成好串

Input Format

第一行包含一个整数n。

第二行包含一个长为n的01串s。

第三行包含一个整数q。

接下来q行每行两个整数表示l,r。保证子串的长度为2的幂次方，且下标从0开始。

n,q<=5000

Output Format

输出q行，对于每个询问输出对应的答案

8
00000101
3
0 7
2 5
0 3

2 
1 
0