4793: [BJWC2018] 数字统计

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:1 Solved:1

Description

小A 正在研究一些数字统计问题。有一天他突然看到了一个这样的问题:

将[L..R]中的所有整数用M 位二进制数表示(允许出现前导0)。现在将这些数中的每一个作如下变换:

从这个数的最低两位开始,如果这两位都是0,那么X=1,否则X=0。现在将这两位删去,然后将X 放在原来最低位的位置上。重复这个变换直到这个数只剩下一位为止。

例如01001 的变换过程如下:

01001-->0100-->011-->00-->1。

现在的问题是变换后的所有数中,值为Y(Y 为0 或1)的有多少个?

小A 不会了,他想让你帮助他完成这个问题。

Input

输入文件包含多组测试数据。

第一行,一个整数T,表示测试数据的组数。

接下来的T 节,每节对应一组测试数据,格式如下:

第一行,两个整数M、Y。

第二行,两个M 位二进制数L、R。

Output

对于每组测试数据,输出一行,一个二进制数,表示该组测试数据中[L..R]中的所有整数变换后的值为Y 的个数。这里的二进制数不允许出现前导0。

Sample Input Copy

1
3 1
001 101

Sample Output Copy

11

HINT

【数据范围】 

对于 20%的数据:1 ≤ M ≤ 16。

对于 40%的数据:1 ≤ M ≤ 32。

对于 100%的数据:1 ≤ M ≤ 200,1 ≤ T ≤ 50。