小A正在研冗一些数字统计问题.有一天他突然看到了一个这样的问题:
将[L...R]中的所备整数用M位二进制数表示(允许出现前导0).现在将这些数中的每 - 个作如下变换:
从这个数的最低两位开始.如果这两位都是0.那么X=1否则X=0.现在将这两位删去.然后将X放在原来最低位的位置上.重复这个变换直到这个数只剩下一位为止.
现在的问题是变换后的所有数中.值为Y(Y为0或1)的有多少个?
小A不会了.他想让你帮助他完成这个问题.
输入文件包含多组测试数据.
笫一行,一个整数T表示测试数据的组数.
接下来的T节,每节对应一组测试数据.格式如下:
笫一行,两个整数M,Y.
笫二行,两个M位二进制数L,R.
对于每组测试数据.输出一行,一个二进制数,表示该组测试数据中[L...R]中的所有整数变换后的值为Y的个数.这里的二进制数不允许出现前导0.