#5535. String

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

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

串的长度为2的幂次方。

存在两个非负整数x,b，使得i∈[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最少经过多少次区间取反操作变成好串